LESSON 238 OF 414 · PARTIAL SUMS #1

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

Practice O(n * k) Read the full explanation

Given an input array of integers and a positive integer k, find the contiguous subarray of length exactly k with the maximum sum, and return its first and last indices.

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 6

Guided

Ctrl + Enter to check

Maximum Sum Subarray Of Length K in Rust, explained

Problem overview

The function max_sum receives a vector of integers, nums, and a positive integer k. It looks at every contiguous subarray of length exactly k, finds the one with the largest sum, and returns its start and end indices as a vector of two i32 values.

In the example, nums = [5, 6, 1, 2, 6, 6, 4, 3] and k = 3. The window from index 4 to index 6 holds 6, 6 and 4, which add up to 16, more than any other window of three. The function returns [4, 6].

Approach: add up every window

A window of length k is fixed by where it starts. The first window starts at index 0, and the last one must still have room for k elements, so it starts at n - k. That makes n - k + 1 windows. For the example, n = 8 and k = 3 give six windows, starting at 0 through 5.

The six windows of the example have these sums, in order: 12, 9, 9, 14, 16 and 13. The largest, 16, belongs to the window starting at index 4, so the stored answer ends as [4, 6]. The answer vector changes only when the running best improves, which here happens at windows 0, 3 and 4.

The brute force adds up the k elements of each window from scratch and remembers the best sum together with the window's indices. Each of the n - k + 1 windows costs k additions, which is O(n * k) time. A follow-up lesson on this problem slides the window and reuses most of the previous sum, which brings the time down to O(n).

When two windows tie, the earlier one wins here. The comparison is a strict "greater than", so a later window with an equal sum doesn't replace the stored answer. For [1, 3, 2, 2, 3, 1] with k = 2, the windows starting at 1 and 3 both sum to 5, and the answer is [1, 2], the first of them.

Step by step

Create best as i32::MIN. It tracks the largest window sum so far. Window sums can be negative, so the start must lie below every possible sum, and the smallest i32 does.
Create answer, a mutable vector holding the first window's bounds, 0 and k - 1. The starting code has already turned k into a usize, so it is cast back with as i32 for the result.
Loop over the window starts with i from 0 to n - k inclusive, written with ..=.
Sum the window. The slice nums[i..i + k] has exactly k elements, and iter().sum() adds them. The variable is annotated as i32 so that sum() knows what to produce.
Compare and record. If this sum beats best, store it and replace answer with the window's first and last index.
Return answer as the last expression.

The solution in Rust

impl Solution {
    fn max_sum(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize;
        let n = nums.len();
        let mut best = i32::MIN;
        let mut answer = vec![0i32, k as i32 - 1];
        for i in 0..=(n - k) {
            let sum: i32 = nums[i..i + k].iter().sum();
            if sum > best {
                best = sum;
                answer = vec![i as i32, (i + k - 1) as i32];
            }
        }
        answer
    }
}

The Rust details worth a closer look:

Shadowing. let k = k as usize; declares a new k that hides the i32 parameter. From then on k is a usize, the type that indexes and slice bounds need.
The cast and the minus. In k as i32 - 1, the cast binds tighter than the subtraction, so it means (k as i32) - 1. The second index in the loop, (i + k - 1) as i32, does the arithmetic in usize first and casts the result.
Slices. nums[i..i + k] borrows part of the vector without copying it. The upper bound is excluded, which is why a slice of length k starting at i ends at i + k and its last element has index i + k - 1.
Inclusive range. 0..=(n - k) includes n - k. Without the =, the last window would be skipped.
usize subtraction. If k is larger than n, n - k can't go below zero. In a debug build it panics. In an optimized build it wraps to a huge number, and the first slice then panics with an out-of-range message. Either way, a k larger than the vector isn't handled, and the lesson assumes it doesn't happen.
Tail expression. answer has no semicolon, so the function returns it.

Complexity

Time: O(n * k). There are n - k + 1 windows, and summing each one reads k elements. When k is close to n / 2 the cost is about n²/4.

Space: O(1). The slice is a borrowed view, so no window is copied. Only best and the two-element answer are stored.

Edge cases and common mistakes

k equals the length. With k = 8 on the example, n - k is 0, there is one window, and the answer is [0, 7].
k = 1. Every element is its own window. The example returns [1, 1], the first 6, because ties keep the earliest window.
Negative values. For [-5, -2, -7, -1] with k = 2, the window sums are -7, -9 and -8, so the answer is [0, 1]. Starting best at 0 would never accept any of them.
Off-by-one in the slice. nums[i..i + k - 1] sums only k - 1 elements. The slice ends one past the last element it contains.
Returning the sum. The function returns the two indices, not the sum.

Testing

[5, 6, 1, 2, 6, 6, 4, 3] with k = 3 gives [4, 6].
The same vector with k = 8 gives [0, 7].
The same vector with k = 1 gives [1, 1].
[1, 3, 2, 2, 3, 1] with k = 2 gives [1, 2].
[-5, -2, -7, -1] with k = 2 gives [0, 1].

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free