LESSON 234 OF 414 · FREE CODING INTERVIEW QUESTIONS

Maximum Sum Subarray in Rust: O(n²) Brute Force with Running Sums

Practice O(n²) Read the full explanation

Given an input array that may contain both positive and negative integers, find the sum of continuous subarray of numbers which has the largest sum.

Example:

Input: nums = [-2, -5, 6, -2, -3, 1, 5, -6]
Output: 7
Explanation: sum([6, -2, -3, 1, 5]) = 7

Note:

Your algorithm should run in O(n^2) time and use O(1) extra space.

Let's come up with a brute force approach. Brute force tries each and every candidate to our solution. For this problem, the candidates are all the subarrays of nums. How can we try out each subarray?

A subarray is defined by its left endpoint, let's name it index i and its right point, let's name it index j. We should go through each pair of indices (i, j) such that 0 <= i <= j < n, where n is the length of nums. How can we achieve this?

Using two nested for loops! The first loop will try out each possible i between 0 and n - 1. The second loop will be written inside the first one and will try out each possible j between i and n - 1.

for each i : 0 to n - 1:
		for each j : i to n - 1:

We will use a variable maxSum to store the greatest sum found so far and for each pair (i, j), update maxSum with sum(nums[i...j]) if it's the case:

maxSum = nums[0]
for each i : 0 to n - 1:
	for each j : i to n - 1:
		maxSum = max(maxSum, sum(nums[i...j]))
return maxSum

All we have to do now is find a way of getting sum(nums[i...j]) in O(1) time. How can we do this?

One way is using Partial Sums. But that implies using an extra array, which takes O(n) extra space. There is a better way. We can use a variable sum to store the sum of the current subarray sum(nums[i...j]).

maxSum = nums[0]
for each i : 0 to n - 1:
	for each j : i to n - 1:
		maxSum = max(maxSum, sum)
return maxSum

How should we update this variable throught the algorithm to make sure that it always stores the correct sum?

Each time we increment j in the second loop, we should add nums[j] to sum. Also, each time we increment i in the first loop, we start with a new empty subarray so we should reset sum to 0:

maxSum = nums[0]
for each i : 0 to n - 1:
	sum = 0
	for each j : i to n - 1:
		sum += nums[j]
		maxSum = max(maxSum, sum)
return maxSum

STEP 1 OF 7

Guided

Ctrl + Enter to check

Maximum Sum Subarray in Rust, explained

Problem overview

The function max_sum_subarray receives a vector nums of integers that may be positive, negative or zero. It returns the largest sum that a continuous run of elements can have. A continuous run, a subarray, is a slice of the vector: elements next to each other, with no gaps, and at least one element.

For nums = [-2, -5, 6, -2, -3, 1, 5, -6] the answer is 7, from the subarray [6, -2, -3, 1, 5]: 6 - 2 - 3 + 1 + 5 = 7. No other run does better. The statement allows O(n²) time and O(1) extra space.

Approach: try every subarray, but reuse the running sum

A subarray is fixed by its first index i and its last index j, with i <= j. Brute force tries every such pair and keeps the best sum.

The cost depends on how each sum is computed. Adding up nums[i..=j] from scratch for every pair makes the algorithm O(n³). A prefix-sum array would give each sum in constant time, but it needs O(n) extra space, which the statement doesn't allow.

There is a cheaper trick. For a fixed i, move j to the right one step at a time. The subarray from i to j is the previous one plus the single element nums[j]. So one variable, sum, can carry the sum along: reset it to 0 when i changes, and add nums[j] each time j advances. Every pair then costs O(1), which gives O(n²) overall and a few integers of memory.

On the example with i = 2, sum runs through 6, 4, 1, 2, 7 as j goes from 2 to 6. The last value, 7, is the best so far, so max_sum becomes 7.

Step by step

Declare max_sum with let mut and start it at nums[0]. Starting at 0 would be wrong when every number is negative, because the answer is then negative and 0 would beat it. nums[0] is a real subarray sum, so it is a safe starting point.
Loop over the first index: for i in 0..nums.len(). The range stops before nums.len(), so it covers exactly the valid indices.
Declare sum inside that loop, starting at 0i32. Declaring it there resets it for each new i. The i32 suffix pins the type of the literal.
Loop over the last index: for j in i..nums.len(). Starting at i keeps j >= i and includes one-element subarrays.
Add nums[j] to sum. Now sum equals the sum of nums[i..=j].
Compare with max_sum. If sum is greater, store it.
Return max_sum as the last expression, with no semicolon, after both loops finish.

The solution in Rust

impl Solution {
    fn max_sum_subarray(nums: Vec<i32>) -> i32 {
        let mut max_sum = nums[0];
        for i in 0..nums.len() {
            let mut sum = 0i32;
            for j in i..nums.len() {
                sum += nums[j];
                if sum > max_sum {
                    max_sum = sum;
                }
            }
        }
        max_sum
    }
}

The Rust details in this code:

Ranges are half-open. 0..nums.len() includes 0 and excludes nums.len(). To include the end, you would write 0..=n. The loop variables i and j are usize, the type Rust requires for indexing.
The last line is the return value. max_sum has no semicolon, so it is the value of the block and therefore of the function. Adding a semicolon would turn it into a statement, and the function would fail to compile because it would produce () instead of an i32.
let mut sum = 0i32; is the same as let mut sum: i32 = 0;. The variable is mut because += changes it.
Indexing is bounds-checked. nums[j] panics when j is out of range instead of reading stray memory. The loop ranges guarantee it never is.
Overflow wraps in optimized builds. The lessons build with -O, where sum += nums[j] wraps around silently if the total leaves the i32 range. A debug build would panic instead.

Complexity

Time: O(n²). For i = 0 the inner loop runs n times, for i = 1 it runs n - 1 times, and so on down to 1. That is n(n + 1)/2 steps, each of constant cost.

Space: O(1). The code keeps max_sum, sum and the two loop counters. It never copies or slices the input.

Edge cases and common mistakes

All negative numbers. For [-3, -1, -2] the answer is -1, the best single element. The subarray must have at least one element, so the answer can't be 0.
A single element. For [5] the loops run once and the answer is 5.
All positive numbers. The best subarray is the whole vector: [1, 2, 3] gives 6.
Resetting sum in the wrong place. If sum is declared before the outer loop, it keeps its value across different values of i, and later subarrays include elements from earlier ones. Declare it inside the outer loop.
Starting j at 0. The inner loop must start at i, otherwise the code sums runs that begin before the chosen first index.
Overflow. For [1500000000, 1500000000] the true answer is 3,000,000,000, which doesn't fit in an i32. In an optimized build the sum wraps to a negative number, and the function returns 1500000000. Tests with huge values would need i64.
Empty input. nums[0] panics on an empty vector. The lesson's inputs have at least one element.

Testing

[-2, -5, 6, -2, -3, 1, 5, -6] gives 7.
[-3, -1, -2] gives -1.
[5] gives 5.
[1, 2, 3] gives 6.
[-2, 1, -3, 4, -1, 2, 1, -5, 4] gives 6.

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

Start learning free