Start learning free

LESSON 211 OF 338 · PARTIAL SUMS #1

Maximum Sum Subarray of Length K in Go: O(n * k) Brute Force

Practice O(n * k) 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 must find the contiguous block of exactly k elements with the largest sum and return the first and last index of that block as a two-element slice.

    In the example, nums = [5, 6, 1, 2, 6, 6, 4, 3] and k = 3. The window at indices 4 to 6 holds 6, 6 and 4, which add up to 16. No other window of three elements beats that, so the function returns [4 6].

    Approach: try every window

    A slice of length n contains n - k + 1 windows of length k: one starting at each index from 0 to n - k. The brute-force idea is to add up the k elements of each window, compare the total with the best one so far and keep the better window.

    That costs k additions for each of the n - k + 1 windows, so the running time is O(n * k). The extra space is O(1), apart from the two-element answer. This lesson keeps the approach simple on purpose. A second lesson on the same problem slides the window one step at a time, which brings the time down to O(n).

    Step by step

    1. Create best. It holds the largest window sum seen so far. Starting it at -(1 << 62), a huge negative number, guarantees that the first window replaces it, even if every sum is negative. Starting at 0 would be wrong for an all-negative slice.
    2. Create answer as an empty []int. It will hold the start and end indices of the best window.
    3. Loop over window starts. The index i runs from 0 up to and including len(nums)-k. The last window of length k starts exactly there, so the condition is <=.
    4. Reset sum to 0 inside that loop. Each window needs its own total, so the variable is declared per window instead of once before the loop.
    5. Loop over the window's positions. The index idx goes from i while it is less than i+k, which visits exactly k elements.
    6. Add nums[idx] to sum.
    7. Compare after the inner loop. If sum is strictly greater than best, store it in best and replace answer with []int{i, i + k - 1}. The strict comparison keeps the earliest window when two windows tie.
    8. Return answer after both loops.

    The solution in Go

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

    The Go details worth a closer look:

    • := declares and infers. best := -(1 << 62) gives best the type int, because an untyped constant becomes an int by default. Here int has 64 bits, so -(1 << 62), which is -4611686018427387904, fits easily.
    • A slice literal makes a new slice. []int{i, i + k - 1} allocates a fresh two-element slice every time the best sum improves. The old one is simply dropped. []int{} is an empty slice, not nil, though both have length 0.
    • Variables are scoped to their block. sum is created anew on every iteration of the outer loop, so there is no separate reset line. It is also invisible after the loop, which is why the comparison sits inside the outer loop body.
    • The only loop keyword is for. Both loops use the three-part form init; condition; post.
    • No exceptions for bad indices. Reading nums[idx] past the end stops the program with a run-time panic. The loop bounds are what keep every index valid.

    Complexity

    Time: O(n * k). The outer loop runs n - k + 1 times and the inner loop runs k times per window. When k is close to n / 2 the product is about n² / 4, which is why this version is called the brute force.

    Space: O(1). Besides the input, the function keeps a few integers and a two-element slice.

    Edge cases and common mistakes

    • All negative numbers. For [-5, -2, -7] and k = 2 the window sums are -7 and -9, so the answer is [0 1]. A best that starts at 0 would never be replaced, and the function would return an empty slice.
    • Ties. For [2, 2, 2] and k = 2 both windows add up to 4, and the function returns [0 1], the earlier one, because of the strict >.
    • k = 1. Each window is one element, so for [4, 1] the answer is [0 0]: start and end are the same index.
    • k larger than the slice. With [1, 2] and k = 3, the loop condition i <= -1 fails at once and the function returns an empty slice. Handle that case separately if you need a different answer.
    • Off-by-one in the loop bound. Using < instead of <= in the outer loop skips the last window. In the example, that window starts at index 5 and holds 6, 4 and 3.
    • Reporting the length instead of the end index. The end of a window that starts at i is i + k - 1, not i + k.
    • Forgetting to reset sum. If sum were declared before the outer loop, every window would add to the previous total.

    Testing

    • nums = [5, 6, 1, 2, 6, 6, 4, 3], k = 3 gives [4 6].
    • nums = [-5, -2, -7], k = 2 gives [0 1].
    • nums = [2, 2, 2], k = 2 gives [0 1].
    • nums = [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