LESSON 247 OF 414 · PARTIAL SUMS #2

Max Sum of Three Subarrays in Rust: Prefix and Suffix Best Sums

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 22

Guided

Ctrl + Enter to check

RUST · PARTIAL SUMS #2

Max Sum Of Three Subarrays in Rust, explained

Problem overview

The function max_sum_of_three_subarrays receives a vector of integers, nums, with at least three elements. It must pick three non-empty, non-overlapping subarrays (runs of consecutive elements) with the largest possible total sum and return that total. The numbers may be negative.

In the example, nums = [2, 3, -8, 7, -2, 9, -9, 7, -2, 4]. The subarrays [2, 3], [7, -2, 9] and [7, -2, 4] sum to 5 + 14 + 9 = 28, and nothing beats that.

Approach: precompute the best subarray on each side

Fix the middle subarray, from index i to index j. The first subarray then has to live in nums[..i] and the third in nums[j + 1..], and each should be the best possible one in its region. A direct solution recomputes "the best subarray in this slice" for every middle choice, which makes it O(n³).

The same two questions are asked over and over, though, and they only depend on one boundary. So answer them once, for every boundary:

left_max_sum[i] is the maximum subarray sum inside the prefix nums[0..=i];
right_max_sum[i] is the maximum subarray sum inside the suffix nums[i..].

Each table is filled in one pass with Kadane's idea. Keep cur, the best sum of a subarray that ends at the current index. It extends the previous one when that one is positive and starts fresh otherwise: cur = nums[i] + cur.max(0). The best subarray inside the prefix up to i either ends at i, with sum cur, or lies entirely inside the prefix up to i - 1. So left_max_sum[i] is the larger of left_max_sum[i - 1] and cur. The suffix table is the mirror image, scanned from the right.

With both tables the middle loops cost O(1) per middle subarray, and the whole algorithm is O(n²). The next lesson on this problem removes the inner loop too.

Step by step

Store nums.len() in n.
Create left_max_sum as a mutable vector of n zeros of type i32, using vec![0i32; n].
Seed it: left_max_sum[0] = nums[0]. The only subarray in the first prefix is the first element.
Declare cur as a mutable variable starting at nums[0], the best sum of a subarray ending at index 0.
Loop over i from 1 to n - 1.
Update cur to nums[i] + cur.max(0).
Store the prefix answer: left_max_sum[i] is the larger of left_max_sum[i - 1] and cur.
Create right_max_sum the same way, and seed its last entry with nums[n - 1].
Reuse cur, now as the best sum of a subarray starting at the current index. Reset it to nums[n - 1].
Loop from n - 2 down to 0 with (0..n - 1).rev(). The range excludes its end, so it covers 0 to n - 2, and rev() reverses the order.
Update cur with the same formula, then set right_max_sum[i] to the larger of right_max_sum[i + 1] and cur.
Declare max_sum as i32::MIN, since the answer can be negative.
Loop over the start i of the middle subarray from 1 to n - 1, and read sum1 = left_max_sum[i - 1], the best first subarray ending before i.
Declare sum2 as a mutable 0i32, and loop over the end j from i to n - 2.
Add nums[j] to sum2, read sum3 = right_max_sum[j + 1], and update max_sum with sum1 + sum2 + sum3.
Return max_sum as the last expression.

The solution in Rust

impl Solution {
    fn max_sum_of_three_subarrays(nums: Vec<i32>) -> i32 {
        let n = nums.len();

        let mut left_max_sum = vec![0i32; n];
        left_max_sum[0] = nums[0];
        let mut cur = nums[0];
        for i in 1..n {
            cur = nums[i] + cur.max(0);
            left_max_sum[i] = left_max_sum[i - 1].max(cur);
        }

        let mut right_max_sum = vec![0i32; n];
        right_max_sum[n - 1] = nums[n - 1];
        cur = nums[n - 1];
        for i in (0..n - 1).rev() {
            cur = nums[i] + cur.max(0);
            right_max_sum[i] = right_max_sum[i + 1].max(cur);
        }

        let mut max_sum = i32::MIN;
        for i in 1..n {
            let sum1 = left_max_sum[i - 1];
            let mut sum2 = 0i32;
            for j in i..n - 1 {
                sum2 += nums[j];
                let sum3 = right_max_sum[j + 1];
                max_sum = max_sum.max(sum1 + sum2 + sum3);
            }
        }

        max_sum
    }
}

The Rust details worth a closer look:

vec![0i32; n]. The macro builds a vector of n copies of the value. The suffix gives the elements their type, so the later max calls and additions line up with the i32 values in nums.
Reassigning cur. It is declared once with let mut and reassigned in the second part, without a new let. Its type stays i32.
Reverse ranges. A range like n - 2..0 is empty; going downwards needs .rev() on an ascending range. (0..n - 1).rev() yields n - 2, n - 3, ..., 0.
Unsigned indices. i is a usize. Expressions like i - 1 are safe here only because the loop starts at 1, and n - 1 is safe because n is at least 3. A subtraction below zero would panic in a debug build and wrap in an optimized one.
max as a method. left_max_sum[i - 1].max(cur) returns the larger of two integers, so no if is needed.
Wrapping. Optimized builds wrap on i32 overflow silently. The code assumes sums that fit in an i32.

Complexity

Time: O(n²). Each table takes one linear pass. The double loop over the middle subarray visits about n² / 2 pairs, and each pair does constant work: two table reads, an addition and a comparison.

Space: O(n). The two tables hold n integers each. The previous approach used no extra space, and this one trades O(n) memory for an n-fold gain in time.

Edge cases and common mistakes

All numbers negative. For [-1, -2, -3] the answer is -6. Both the tables and max_sum must start from real values, not 0.
Exactly three numbers. The only pass is i = 1, j = 1. The tables give the first and last elements, and the answer is the sum of all three.
Off-by-one on the table indices. The first subarray must end before the middle one starts, hence left_max_sum[i - 1]. The third must start after it ends, hence right_max_sum[j + 1]. Using i or j would let subarrays overlap.
Allowing j to reach n - 1. Then right_max_sum[j + 1] would index past the end and panic. The bound n - 1 in i..n - 1 prevents it.
Treating a table entry as "subarray ending here." left_max_sum[i] is the best anywhere in the prefix, which is what lets the first subarray end well before the middle one.
Mixed signs. For [4, -1, 4, -1, 4] the answer is 12.

Testing

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

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

Start learning free