Maximum Sum Subarray of Size K

Q: What is the time complexity of the maximum sum subarray of size k?

With a sliding window it is O(n) time and O(1) extra space: one sum for the first window, then one addition and one subtraction per step. Adding up every window separately is O(n·k) .

Q: How is this different from the maximum subarray problem?

Here the length is fixed at k , so a sliding sum covers every candidate. In the maximum subarray problem the length is free, and Kadane's algorithm decides at each element whether to extend the current run or start a new one. A fixed window never has that choice.

Q: Can prefix sums solve it too?

Yes. Let prefix[i] be the sum of the first i elements; the window starting at s sums to prefix[s+k] - prefix[s] . That is also O(n) time, but it stores n+1 totals where the sliding window needs two variables.

EasySliding window

+10

You get an array of integers nums and a window length k. Look at every run of exactly k neighbouring elements and return the largest sum among them. The values can be negative, so the answer can be negative too.

Function

maxSumSubarray(nums: integer-array, k: integer) → integer

numsinteger-array: the array of integers
kinteger: how many neighbouring elements each window holds
Returnsinteger: the largest sum of any k consecutive elements

Constraints

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴

Examples

Input: nums = [4, -1, 3, 7, -2, 5, 1]k = 3
Output: 10
Explanation: The five windows of length 3 add up to 6, 9, 8, 10 and 4. The largest is 7 + (-2) + 5 = 10.

Input: nums = [-3, -8, -1, -6]k = 2
Output: -7
Explanation: Every value is negative, so every window sum is too: -11, -9 and -7. The largest of them is -1 + (-6) = -7.

Input: nums = [5, -2, 4]k = 3
Output: 7
Explanation: When k equals the length of the array there is one window, the whole array, and 5 + (-2) + 4 = 7.

Follow-up

Can you also return where the best window starts, picking the leftmost one when several windows tie?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

There are n-k+1 windows, and adding each one up from scratch costs k additions. Neighbouring windows share all but two elements, so slide the window instead of rebuilding it: one value enters, one value leaves, and each new sum costs two operations.

Add up every window

Correct, but does not finish on the largest tests

Intuition

A window is fixed by its start, from index 0 to n-k; a later start would run past the end. For each start, add the k elements and compare the total with the best so far. Every window is checked, so the best one is found.

The cost is (n-k+1) × k additions, largest when k is about half of n: 5001 × 5000, about 2.5 × 10^7, for n = 10^4 and k = 5000. Almost all of them repeat work done for the window before.

Algorithm

Set best to the smallest possible value.
For each start from 0 to n-k, set total = 0.
Add nums[start] through nums[start+k-1] to total.
If total beats best, store it.
Return best.

def maxSumSubarray(nums, k):
    n = len(nums)
    best = None
    for start in range(n - k + 1):
        total = 0
        for i in range(start, start + k):
            total += nums[i]
        if best is None or total > best:
            best = total
    return best

Slide a fixed window

Intuition

In the first example the windows starting at 0 and 1 sum to 6 and 9. Both hold -1 and 3, so the second sum is the first plus the 7 that entered minus the 4 that left: 6 + 7 - 4 = 9.

That holds at every step. When the right end moves to index i, nums[i] enters and nums[i-k] leaves. Add up the first window once, then update the sum with one addition and one subtraction per step, and keep the largest sum you see.

Algorithm

Add up nums[0] through nums[k-1] into window.
Set best = window.
For every i from k to n-1, add nums[i] and subtract nums[i-k].
After each step, set best to the larger of best and window.
Return best.

def maxSumSubarray(nums, k):
    # Sum of the first window, nums[0..k-1].
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        # Slide one step right: nums[i] enters, nums[i-k] leaves.
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

Pitfalls and edge cases

Starting best at 0. On [-3, -8, -1, -6] with k = 2 it is never beaten, and you return 0 instead of -7.
Subtracting the wrong element. When nums[i] enters, nums[i-k] leaves; nums[i-k+1] or nums[i-k-1] gives windows of the wrong length.
Stopping one start too early. The last window starts at n-k. With [5, -2, 4] and k = 3 it is the only window, and an off-by-one returns the starting value of best.
Comparing only inside the loop. In [9, 1, 1] with k = 2 the first window, 10, is the best, so set best to it before the loop.

Frequently asked questions3

What is the time complexity of the maximum sum subarray of size k?

With a sliding window it is O(n) time and O(1) extra space: one sum for the first window, then one addition and one subtraction per step. Adding up every window separately is O(n·k).

How is this different from the maximum subarray problem?

Here the length is fixed at k, so a sliding sum covers every candidate. In the maximum subarray problem the length is free, and Kadane's algorithm decides at each element whether to extend the current run or start a new one. A fixed window never has that choice.

Can prefix sums solve it too?

Yes. Let prefix[i] be the sum of the first i elements; the window starting at s sums to prefix[s+k] - prefix[s]. That is also O(n) time, but it stores n+1 totals where the sliding window needs two variables.

def maxSumSubarray(nums, k):
    # Write code here

Test #1

Test #2

Test #3

Arguments

nums = [4, -1, 3, 7, -2, 5, 1]
k = 3

Expected Output