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

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)