Start learning free

LESSON 212 OF 338 · PARTIAL SUMS #1

Maximum Sum Subarray of Length K in Go: O(n) Sliding Window

Practice O(n) Read the full explanation

Given an input array of integers and a positive integer k, find out the maximum sum of a contiguous subarray of length exactly k

Example

Input: nums = [5, 6, 1, 2, 6, 6, 4, 3], k = 3
Output: 4 6
Explanation: The subarray nums[4...6] has the maximum sum of 16
STEP 1 OF 8
    Ctrl + Enter to check

    GO · PARTIAL SUMS #1

    Maximum Sum Subarray Of Length K in Go, explained

    Problem overview

    The function maxSum receives a slice of integers, nums, and a positive integer k. It returns the first and last index of the contiguous block of exactly k elements with the largest sum, as a two-element slice.

    For nums = [5, 6, 1, 2, 6, 6, 4, 3] and k = 3, the block at indices 4 to 6 (6, 6, 4) adds up to 16, the largest of all windows, so the answer is [4 6].

    Approach: slide the window

    The brute force adds up k elements for every window, which costs O(n * k). But two neighbouring windows share k - 1 elements. Moving from the window that starts at i - 1 to the one that starts at i drops exactly one element, nums[i-1], and adds exactly one, nums[i+k-1]. So each new sum is the old sum minus one value plus another, in constant time.

    The plan is to compute the first window's sum once with k additions, then slide across the rest of the slice with one subtraction and one addition per step. The total is O(n).

    Step by step

    1. Start answer with the first window, []int{0, k - 1}. If no later window is better, this is the result, so an empty starting value would be wrong.
    2. Declare sum as 0. It will always hold the sum of the current window.
    3. Add the first k elements with a loop over indices 0 to k - 1. Now sum is the first window's sum.
    4. Declare maxSum and set it to sum. The first window is the best one seen so far.
    5. Loop over the remaining starts, i from 1 to len(nums)-k inclusive. The last window starts at len(nums)-k, so the condition uses <=.
    6. Slide. Subtract nums[i-1], the element that just left the window, and add nums[i+k-1], the one that just entered.
    7. Compare. If sum is strictly greater than maxSum, update maxSum and set answer to []int{i, i + k - 1}. The strict comparison keeps the earliest window on a tie.
    8. Return answer.

    The solution in Go

    func maxSum(nums []int, k int) []int {
    answer := []int{0, k - 1}
    sum := 0
    for i := 0; i < k; i++ {
        sum += nums[i]
    }
    maxSum := sum
    for i := 1; i <= len(nums)-k; i++ {
        sum = sum - nums[i-1] + nums[i+k-1]
        if sum > maxSum {
            maxSum = sum
            answer = []int{i, i + k - 1}
        }
    }
    return answer
}

    Go details to notice:

    • A local variable can reuse the function's name. Inside maxSum, the line maxSum := sum declares a variable with the same name as the function. That is legal because the new name shadows the function within its scope. It works here since the function never calls itself, but a different name such as best is safer.
    • Plain = against :=. sum = sum - nums[i-1] + nums[i+k-1] updates the existing variable. Writing := there would declare a new sum inside the loop and leave the outer one unchanged.
    • Index expressions are checked. If the slice is shorter than k, nums[i] in the first loop panics with an index-out-of-range error. Go never reads past the end silently.
    • len(nums)-k can be negative, because int is signed. That is why the loop condition simply fails instead of wrapping around.

    Tracing the example

    With nums = [5, 6, 1, 2, 6, 6, 4, 3] and k = 3, the first window 5, 6, 1 has sum 12, so sum and maxSum start at 12 and answer is [0 2].

    • i = 1: subtract 5, add 2. The sum is 9, which is not better.
    • i = 2: subtract 6, add 6. The sum is 9.
    • i = 3: subtract 1, add 6. The sum is 14, which beats 12, so answer becomes [3 5].
    • i = 4: subtract 2, add 4. The sum is 16, a new best, so answer becomes [4 6].
    • i = 5: subtract 6, add 3. The sum is 13, which is not better.

    The loop ends after i = 5 because len(nums)-k is 5, and the function returns [4 6]. Each step touched only two elements of the slice, instead of three, and the saving grows with k: for a window of 1,000 elements it is two operations instead of 1,000 per step.

    Complexity

    Time: O(n). The first loop does k additions and the second does at most n - k iterations of constant work, so the total is at most n steps.

    Space: O(1). The function keeps a few integers and the two-element answer.

    Edge cases and common mistakes

    • The first window is the best. For [9, 1, 1, 1] and k = 2 the answer is [0 1]. This is why answer starts as the first window.
    • All negative numbers. For [-5, -2, -7] and k = 2 the answer is [0 1]. Because maxSum starts from a real window sum and not from 0, negative totals work.
    • Ties. For [2, 2, 2] and k = 2, both windows sum to 4 and the answer is [0 1].
    • k equal to the length. There is one window, the loop body never runs, and the answer is [0, k - 1].
    • Wrong element leaving the window. The element to subtract is nums[i-1], not nums[i]. The element to add is nums[i+k-1], the last element of the new window.
    • k larger than the slice. With [1, 2] and k = 3 the first loop panics, so check the length first if such input is possible.

    Testing

    • [5, 6, 1, 2, 6, 6, 4, 3], k = 3 gives [4 6].
    • [-5, -2, -7], k = 2 gives [0 1].
    • [2, 2, 2], k = 2 gives [0 1].
    • [4, 1], k = 1 gives [0 0].
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free