Maximum subarray sum with at most K elements

Question

Maximum subarray sum with at most K elements :

Given an array of integers and a positive integer k, find the maximum sum of a subarray of size less than or equal to k. A subarray is a contiguous part of the array. For example, if the array is [5, -3, 5, 5, -3, 5] and k is 3, then the maximum subarray sum with at most k elements is 10, which is obtained by the subarray [5, 5]

My initial thought was to use the Kadane's algorithm with a sliding window of K. Below is the code:

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

but this approach won't work for the test case -

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

Edit: I found the solution - Prefix Sum + Monotonic Deque - O(n) Time complexity

def maxSubarraySum(self, nums, k) -> int:
    prefix_sum = [0] * len(nums)
    prefix_sum[0] = nums[0]
    for i in range(1, len(nums)):
        prefix_sum[i] = prefix_sum[i-1] + nums[i]
    q = deque()
    for i in range(k):
        while len(q) > 0 and prefix_sum[i] >= prefix_sum[q[-1]]:
            q.pop()
        q.append(i)
    maxi = max(prefix_sum[:k])
    for i in range(1, len(nums)):
        if q[0] < i:
            q.popleft()
        if i + k - 1 < len(nums):
            while len(q) > 0 and prefix_sum[i + k - 1] >= prefix_sum[q[-1]]:
                q.pop()
            q.append(i + k - 1)
        maxi = max(maxi, prefix_sum[q[0]] - prefix_sum[i-1])
    return maxi

Answer 1

There is an O(n) solution at https://cs.stackexchange.com/a/151327/10147

We can have O(n log n) with divide and conquer. Consider left and right halves of the array: the solution is either in (1) the left half exclusively, (2) the right half exclusively, or (3) a suffix of the left combined with a prefix of the right.

To solve (3) in O(n), iterate from the middle to the left, recording for each index the higher of the highest seen or the total sum. Then iterate to the right and add a similar record for prefix length l with the recorded value for index k - l (or the longest possible if k-l is out of bounds) in the first iteration.

For the example, [5, -3, 5, 5, -3, 5] k = 3, we have:

[5, -3, 5, 5, -3, 5]
 7   5  5 <---
     --->  5   5  7
     ^-----^
       best = 5 + 5 = 10

Answer 2

Here is a similar solution which is a bit more explicit:

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)

Answer 3

The basic issue in your code is it is always taking some of 3 elements after 3rd iteration.

Iterations :

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

It is difficult to achieve expected result in single loop.

Suggestion : you should always try to debug your code, first manually and still facing issue you can take help of GDB online for further debugging.

This is what I wrote as a solution to above statement.

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)

Answer 4

When you drop the first element

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

the new range may start with a negative number. This is never good. You might be tempted to drop all negatives as well:

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

But this is not enough because the new range may still have a prefix sum less than zero, which would require restarting the range at that point.

Answer 5

Apologies if I've misinterpreted your question, but as I understand it, you want to find the largest value that can be summed in a range (as small as 1 or as large as 'k') in your array.

I've wrote a quick code that does just that, let me know if it falls short in anyway.

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)

Answer 6

Use two indices.

On each iteration:

First, advance the rear index when:

• The sum between the two indices is <= 0
• The distance between the two indices (inclusive) is k
• The forward index is at the end of the array
• The value of the element at the rear index is <= 0

Then, advance the forward index when:

• We didn't advance the rear index
• We advanced the rear index past the forward index

Keep track of the current & best sum between indices. Updates are O(1) since we just need to adjust for the element being included or excluded from the range between our indices.

Stop when the rear index reaches the end of the array.

If you want the matching indices as well, store these every time you find a new best sum.

Ruby code (read as pseudocode if Ruby is unfamiliar)

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

Sample Results

> 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]