最多 K 个元素的最大子阵列总和-解网

问：

最多 K 个元素的最大子阵列总和：

给定一个整数数组和一个正整数 k，求大小小于或等于 k 的子数组的最大和。子数组是数组的连续部分。例如，如果数组是并且 k 是，则包含最多元素的最大子数组和是，它由子数组获得[5, -3, 5, 5, -3, 5]3k10[5, 5]

我最初的想法是使用 Kadane 算法和 K 的滑动窗口。下面是代码：

maxi = nums[0]
max_so_far = 0
prev = 0
for i in range(len(nums)):
    max_so_far += nums[i]
    if (i - prev) >= k:
        max_so_far -= nums[prev]
        prev += 1
    maxi = max(maxi, max_so_far)
    if max_so_far < 0:
        max_so_far = 0
        prev = i + 1
return maxi

但这种方法不适用于测试用例 -

nums = [5, -3, 5, 5, -3, 5]
k = 3

python 数组算法数据结构

arr = [5, -3, 5, 5, -3, 5]
k = 3

max_sum = 0

for e,i in enumerate(arr): #Run through array

    for j in range(k): #Run through range length values 1 - k

        sub_sum_of_range = 0
        value_list = []

        for l in range(j, j+1): #Use range length values to calculate largest sum possible

            if e+l < len(arr): #if array len is 6, don't allow code to calculate arr[6]
                value_list.append(arr[e+l]) #Current list being summed
                sub_sum_of_range = sub_sum_of_range + arr[e+l]

                if sub_sum_of_range > max_sum: #If sum is greater than current max, replace it
                    max_sum = sub_sum_of_range
                    max_value_list = value_list

print(max_sum)
print(max_value_list)

1赞 Sachin Mirajkar 11/17/2023 #2

代码中的基本问题是，在第三次迭代后，它总是采用 3 个元素中的一些元素。

迭代：

1:sum_so_far = 5 maxi = 5

2:sum_so_far = 5+(-3) maxi = 5

3:sum_so_far = 5+(-3)+5 maxi = 7

4:sum_so_far = (-3)+5+5 maxi = 7

5:sum_so_far = 5+5+(-3) maxi = 7

6:sum_so_far = 5+(-3)+5 maxi = 7

单循环很难达到预期的效果。

建议：您应该始终尝试调试您的代码，首先手动调试，但仍然面临问题，您可以在线帮助 GDB 进行进一步调试。

这就是我写的，作为上述陈述的解决方案。

ar = [5, -3, 5, -5, -30, 50]
k = 3 
sub_sum = 0
temp_list = []
sum_list = []
for i in range(len(ar)):
    temp,j = 0,0
    while (i+j) < len(ar):
        temp += ar[i+j]
        temp_list.append(ar[i+j])
        j += 1
    if temp > sub_sum :
        sub_sum = temp
        sum_list = temp_list.copy()
    temp_list = []

print (sub_sum)
print (sum_list)

DEBUG = True
  
def log(msg):
    if DEBUG:
        print(msg)

def calc_max_window(nums, k):
    nums_len = len(nums)
    assert k <= nums_len, f"k must be less or equal to {nums_len}"
    max_sum = 0
    max_window = []
    log(f"Array to check: {nums}")
    for window_size in range(1, k + 1):
        log(f"Checking windows of size: {window_size}")
        for i in range(nums_len - window_size + 1):
            window = nums[i:i + window_size]
            log(f"\tChecking window: {window}")
            sum_window = sum(window)
            if sum_window > max_sum:
                log(f"\t\tWindow is new max: {sum_window}")
                max_sum, max_window = sum_window, window
    log(f"max_sum: {max_sum}, max_window: {max_window}")
    return max_window, max_sum


nums = [5, -3, 5, 5, -3, 5]
calc_max_window(nums, 3)

0赞 n. m. could be an AI 11/18/2023 #4

当您删除第一个元素时

if (i - prev) >= k:
    max_so_far -= nums[prev]
    prev += 1

新范围可能以负数开头。这从来都不是好事。您可能还想放弃所有负面因素：

if (i - prev) >= k:
    max_so_far -= nums[prev]
    prev += 1
    while prev < i and nums[prev] < 0:
        max_so_far -= nums[prev]
        prev += 1

但这还不够，因为新范围的前缀总和可能仍小于零，这需要在此时重新启动范围。

1赞 Dave 11/19/2023 #5

使用两个索引。

在每次迭代中：

首先，在以下情况下前进后索引：

两个指数之间的总和为 <= 0
两个指数（含）之间的距离为 k
前向索引位于数组的末尾
后索引处的元素值为 <= 0

然后，在以下情况下推进远期索引：

我们没有推进后索引
我们将后向索引推进到前向索引之上

跟踪指数之间的当前和最佳总和。更新是 O（1），因为我们只需要调整索引之间的范围包含或排除的元素。

当后索引到达阵列末尾时停止。

如果您还需要匹配的指数，请在每次找到新的最佳总和时存储这些指数。

Ruby 代码（如果不熟悉 Ruby，则读取为伪代码）

def f(arr, k)
  cur = arr[0]
  best = arr[0]
  best_indices = [0,0]
  i = 0
  j = 0
  
  while j <= arr.length - 1 && i < arr.length - 1
    if cur <= 0 || j-i+1 == k || j == arr.length - 1 || arr[i] <= 0
      cur -= arr[i]
      i += 1
      if j < i
        j += 1
        cur += arr[j]
      end
    else
      j += 1
      cur += arr[j]
    end
    if cur > best
      best = cur
      best_indices = [i, j]
    end
  end
  puts "best = #{best}, range = [#{best_indices[0]}, #{best_indices[1]}]"
end

示例结果

> f([1,1,1,1,1,1,1,1,1,1,-10000,1,1,1], 5)
best = 5, range = [0, 4]

> f([1,1,1,1,-10000,1,1,1], 5)
best = 4, range = [0, 3]

> f([1,1,1,-10000,1,1,1,1], 5)
best = 4, range = [4, 7]

> f([1,1,26,26,-100,26,26,1,1,1,1], 5)
best = 55, range = [5, 9]

> f([-100, -100, 26,26,-100,26,26,-100,1,1,1], 5)
best = 52, range = [2, 3]

> f([-100, -100, 70,70,-100,70,70,-100,1,1,1], 5)
best = 180, range = [2, 6]

最多 K 个元素的最大子阵列总和

Maximum subarray sum with at most K elements

评论

评论

评论