Maximum subarray sum with at most K elements

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

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