LESSON 237 OF 414 · PARTIAL SUMS #1

Max Sum of Three Subarrays in Rust: Brute Force with Six Loops

Practice O(n⁶) Read the full explanation

Given an array nums of integers, find three non-overlapping subarrays with maximum sum.

Return the total sum of the three subarrays

Example:

Input: [2, 3, -8, 7, -2, 9, -9, 7, -2, 4]
Output: 28
Explanation: Subarrays [2, 3], [7, -2, 9] and [7, -2, 4]
             have the maximum sum of 28

Note:

Subarrays must be non-empty
nums contains at least three numbers

STEP 1 OF 16

Guided

Ctrl + Enter to check

RUST · PARTIAL SUMS #1

Max Sum Of Three Subarrays in Rust, explained

Problem overview

The function max_sum_of_three_subarrays takes a vector of integers with at least three elements. It must choose three non-empty subarrays that don't overlap and return the largest possible total of their sums. A subarray is a continuous run of elements.

In the example, [2, 3, -8, 7, -2, 9, -9, 7, -2, 4], the best choice is [2, 3], [7, -2, 9] and [7, -2, 4], with sums 5, 14 and 9, so the answer is 28. The -8 and -9 between the groups are left out, which is allowed: the subarrays don't have to touch.

Approach: try every triple

This lesson is the brute force, the baseline that later lessons on the same problem improve on. A subarray is fixed by its first and last index. Three non-overlapping subarrays, in left to right order, are fixed by six indexes that satisfy

i1 <= j1 < i2 <= j2 < i3 <= j3

Six nested loops walk through all such sextuples. Each loop starts where the previous one ended: j1 starts at i1, i2 starts at j1 + 1, and so on. That keeps every subarray non-empty and strictly after the one before it. Every unordered choice of three subarrays appears exactly once, in order.

The sums are built incrementally. When the end index j1 moves one step right, sum1 grows by one element. There is no inner loop that re-adds the whole subarray. Each running sum is declared in the loop where its subarray starts, so it resets to 0 for every new start.

The answer is the maximum of sum1 + sum2 + sum3 over all triples.

Step by step

Store n. nums.len() is a usize and is used in every loop, so it gets a name.
Create max_sum as i32::MIN. The best total can be negative, so 0 would be wrong. The smallest i32 is below any total that can occur, so the first triple always replaces it.
Loop over i1, the start of the first subarray, from 0 to the end of the vector.
Declare sum1 as 0i32. The suffix gives it the same type as the elements.
Loop over j1, the end of the first subarray, from i1 on.
Add nums[j1] to sum1 in that loop.
Loop over i2 from j1 + 1, the start of the second subarray.
Declare sum2 in the same way as sum1.
Loop over j2 from i2.
Add nums[j2] to sum2.
Loop over i3 from j2 + 1.
Declare sum3.
Loop over j3 from i3.
Add nums[j3] to sum3.
Update max_sum with sum1 + sum2 + sum3 in the innermost loop.
Return max_sum after the outermost loop, as the final expression without a semicolon.

The solution in Rust

impl Solution {
    fn max_sum_of_three_subarrays(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut max_sum = i32::MIN;
        for i1 in 0..n {
            let mut sum1 = 0i32;
            for j1 in i1..n {
                sum1 += nums[j1];
                for i2 in j1 + 1..n {
                    let mut sum2 = 0i32;
                    for j2 in i2..n {
                        sum2 += nums[j2];
                        for i3 in j2 + 1..n {
                            let mut sum3 = 0i32;
                            for j3 in i3..n {
                                sum3 += nums[j3];
                                max_sum = max_sum.max(sum1 + sum2 + sum3);
                            }
                        }
                    }
                }
            }
        }
        max_sum
    }
}

The Rust details worth a closer look:

Ranges. a..b includes a and excludes b. When a is not below b, the range is empty and the loop body simply doesn't run. That is what happens for j1 + 1..n when j1 is the last index, and it is why no explicit bounds checks appear.
Operator precedence. In j1 + 1..n, the addition binds tighter than .., so it means (j1 + 1)..n.
usize indexes. The loop variables are usize because they come from ranges over n, and Rust indexes vectors with usize. No casts are needed, but also no subtraction below zero is ever done.
0i32. A literal suffix fixes the type of a number literal. Here it matches the elements, although inference would also reach i32 from += with nums[j1].
i32::MIN. It is an associated constant of the type, -2,147,483,648.
Overflow. In the optimized build sum1 + sum2 + sum3 wraps silently. For [i32::MAX, i32::MAX, 1] the function returns -1, which is a wrapped result, not a real total. A debug build would panic on that addition.

Complexity

Time: O(n⁶). There are six nested loops, each running over up to n positions. Because each loop starts after the previous one, the innermost line runs exactly "n + 3 choose 6" times, which is 1,716 for n = 10, 6,096,454 for n = 40 and 377,447,148 for n = 80. Doubling n multiplies the work by about 62. The ordering makes the constant small, but the growth is still the sixth power, so the method only suits short inputs.

Space: O(1). Six indexes, three running sums and the best total.

Edge cases and common mistakes

Exactly three elements. [-1, -2, -3] returns -6. Each element must form its own subarray, and the loops find that single triple.
All negative numbers. [-5, -1, -2, -9, -3] returns -6, from the elements -1, -2 and -3. This is why max_sum starts at i32::MIN rather than 0.
Overlap. Starting i2 at j1 instead of j1 + 1 would let two subarrays share an element and count it twice.
Sums that don't reset. Declaring sum2 or sum3 outside its loop would carry the old total into the next start.
All elements used. [1, 2, 3, 4] returns 10. The three subarrays may leave elements out, but when all values are positive the best choice covers everything.

Testing

[2, 3, -8, 7, -2, 9, -9, 7, -2, 4] gives 28.
[-1, -2, -3] gives -6.
[-5, -1, -2, -9, -3] gives -6.
[1, 2, 3, 4] gives 10.

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

Start learning free