LESSON 248 OF 414 · PARTIAL SUMS #2

Max Sum of Three Subarrays in Rust: O(n) with Prefix and Suffix Tables

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 21

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) whose combined sum is as large as possible, and return that sum. 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] add up to 5 + 14 + 9 = 28, the best possible.

Approach: a linear pass over the end of the middle subarray

The natural way to solve this is to fix the middle subarray, from k to i. The first subarray is then the best one inside the prefix before k, and the third is the best one inside the suffix after i. Two tables give those answers in constant time:

left_max_sum[x]: the maximum subarray sum inside nums[0..=x];
right_max_sum[x]: the maximum subarray sum inside nums[x..].

Even so, trying every pair (k, i) is O(n²). This lesson removes the loop over k with a rewrite. Let P[x] be the sum of nums[0..=x]. The middle subarray from k to i sums to P[i] - P[k - 1], so the total is

left_max_sum[k - 1] + (P[i] - P[k - 1]) + right_max_sum[i + 1]
= P[i] + right_max_sum[i + 1] + (left_max_sum[k - 1] - P[k - 1])

The last bracket depends only on k, and the first two terms only on i. For a fixed i, the best k is the one that maximizes the bracket among all starts k up to i. Call that maximum max_diff. As i moves right, one new start becomes available, so max_diff is updated with one comparison instead of a loop.

In the example, take i = 5, the end of [7, -2, 9]. Here P[5] = 11 and right_max_sum[6] = 9. The best start is k = 3, where left_max_sum[2] - P[2] = 5 - (-3) = 8. The total is 11 + 9 + 8 = 28.

Step by step

Store nums.len() in n.
Create left_max_sum as a mutable vector of n zeros of type i32 and seed left_max_sum[0] with nums[0].
Declare cur, the best sum of a subarray ending at the current index, starting at nums[0].
Loop over i from 1 to n - 1. Update cur to nums[i] + cur.max(0): extend the previous run if it is positive, start fresh otherwise.
Fill the table: left_max_sum[i] is the larger of left_max_sum[i - 1] and cur. The best subarray in the prefix either ends at i or lies before it.
Create right_max_sum the same way, seed its last entry with nums[n - 1], and reset cur to nums[n - 1], now the best sum of a subarray starting at the current index.
Loop from n - 2 down to 0 with (0..n - 1).rev(), updating cur with the same formula and setting right_max_sum[i] to the larger of right_max_sum[i + 1] and cur.
Declare max_sum as i32::MIN, because the answer can be negative.
Declare partial_sum, starting at nums[0]. At the start of each pass over i it holds the sum of everything before index i.
Declare max_diff at i32::MIN. It will hold the largest value of left_max_sum[k - 1] minus the sum before k, over all the starts k seen so far.
Loop over i, the last index of the middle subarray, from 1 to n - 2. It needs a first subarray before it and a third after it.
Offer index i as a start: max_diff becomes the larger of itself and left_max_sum[i - 1] - partial_sum. At this point partial_sum is still the sum before i, as the formula needs. This must happen before the next step, because the middle subarray can consist of the single element nums[i].
Add nums[i] to partial_sum, so it now holds P[i].
Update the answer: max_sum becomes the larger of itself and partial_sum + right_max_sum[i + 1] + max_diff.
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;
        let mut partial_sum = nums[0];
        let mut max_diff = i32::MIN;
        for i in 1..n - 1 {
            max_diff = max_diff.max(left_max_sum[i - 1] - partial_sum);
            partial_sum += nums[i];
            max_sum = max_sum.max(partial_sum + right_max_sum[i + 1] + max_diff);
        }

        max_sum
    }
}

The Rust details worth a closer look:

vec![0i32; n]. It builds a vector of n copies of 0, and the suffix fixes the element type to i32.
(0..n - 1).rev(). Ranges only count upwards, so a descending loop reverses an ascending one. The range excludes its end, so this visits n - 2 down to 0.
Reusing cur. The second use is a plain assignment, cur = nums[n - 1], with no let, because the variable already exists and is mutable.
Safe unsigned subtraction. The indices are usize. Expressions such as i - 1 are safe because the loops start at 1, and n - 1 is safe because n is at least 3. Below zero, a debug build panics and an optimized build wraps.
i32::MIN as a start. max_diff is always replaced before it is used, since the first pass sets it from a real value, so the sum partial_sum + ... + max_diff never adds i32::MIN.
Wrapping. With optimizations, i32 overflow wraps silently. The code assumes sums that fit in an i32.

Complexity

Time: O(n). Two passes build the tables and one pass combines them. Each pass does constant work per element.

Space: O(n). The two tables hold n integers each. Everything else is a handful of scalars.

Edge cases and common mistakes

All numbers negative. For [-1, -2, -3] the answer is -6, and for [-5, -1, -3, -2] it is -6 as well. Starting max_sum at 0 would give a wrong answer.
Exactly three numbers. The loop runs once, with i = 1, and the three single elements are the only choice.
Swapping the two updates. If partial_sum += nums[i] came before the max_diff update, the new start i would be offered with the sum including nums[i], which is the wrong prefix.
Using the wrong bounds. The loop ends at n - 2 so that right_max_sum[i + 1] exists. A bound of n would index past the end.
Mixed signs. For [4, -1, 4, -1, 4] the answer is 12, three separate 4s. For [1, 2, 3, 4] it is 10.
Not checking against a slower version. A rewrite like this one is easy to get subtly wrong. Compare it against the version with two loops on small random inputs.

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