Start learning free

LESSON 246 OF 414 · PARTIAL SUMS #2

Max Sum of Three Subarrays in Rust: Enumerate the Middle, Use Kadane

Practice O(n3) 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 17
    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 choose three non-empty, non-overlapping subarrays (runs of consecutive elements) so that their combined sum is as large as possible, and return that sum. The numbers may be negative, so the result can be negative too.

    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, which is the best possible.

    Approach: fix the middle subarray

    Choosing three subarrays at once means six boundaries, which is a lot of loops. The lesson reduces the problem by fixing only the middle subarray, from index i to index j. Once it is fixed:

    • the first subarray must lie entirely in nums[..i], and the best choice there is the maximum subarray sum of that prefix;
    • the third must lie in nums[j + 1..], and its best choice is the maximum subarray sum of that suffix.

    The three choices don't interact, so each one can be optimized separately. The maximum subarray sum of a slice is a known problem with a one-pass solution, Kadane's algorithm, and the lesson calls it as a helper, max_sum_subarray.

    The cost is the plain version of the idea: every middle subarray calls the helper twice, on slices of length up to n. That gives O(n³) time. The other lessons on this problem speed this up by precomputing the best prefix and suffix sums. This one keeps the code short and shows the structure of the answer.

    For the example, take i = 3 and j = 5. The middle is [7, -2, 9] with sum 14. The prefix [2, 3, -8] has best subarray sum 5 and the suffix [-9, 7, -2, 4] has best subarray sum 9. The total is 28.

    Step by step

    1. Store nums.len() in n. The loops use it many times.
    2. Declare max_sum as a mutable i32 starting at i32::MIN. Starting at 0 would be wrong, because the answer can be negative.
    3. Loop over i, the first index of the middle subarray, from 1 to n - 1. It starts at 1 so the first subarray has at least one element. At i = n - 1 there is no room for a third subarray, and the inner loop simply doesn't run.
    4. Compute sum1 as the maximum subarray sum of &nums[..i]. The slice borrows part of the vector without copying it, and ..i excludes i.
    5. Declare sum2 as a mutable 0i32, the sum of the middle subarray so far. It is declared inside the loop over i, so every start begins at 0.
    6. Loop over j, the last index of the middle subarray, from i to n - 2, so the third subarray keeps at least one element.
    7. Extend the middle: add nums[j] to sum2. Growing the subarray one element at a time avoids re-adding it from scratch.
    8. Compute sum3 as the maximum subarray sum of &nums[j + 1..], a slice that runs to the end.
    9. Update the answer with the larger of max_sum and sum1 + sum2 + sum3.
    10. Return max_sum after the outer loop, with no semicolon.
    11. Write the helper max_sum_subarray, which takes a slice &[i32]. It keeps result, the best sum so far, starting at nums[0] (not 0, because all numbers may be negative), and max_sum, the best sum of a subarray ending at the current element. For each val, max_sum becomes val + max_sum.max(0): it extends the previous run when that run is positive, and starts fresh otherwise. Then result takes the larger of itself and max_sum.

    The solution in Rust

    impl Solution {
    fn max_sum_subarray(nums: &[i32]) -> i32 {
        let mut result = nums[0];
        let mut max_sum = 0i32;
        for &val in nums {
            max_sum = val + max_sum.max(0);
            result = result.max(max_sum);
        }
        result
    }

    fn max_sum_of_three_subarrays(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut max_sum = i32::MIN;
        for i in 1..n {
            let sum1 = Solution::max_sum_subarray(&nums[..i]);
            let mut sum2 = 0i32;
            for j in i..n - 1 {
                sum2 += nums[j];
                let sum3 = Solution::max_sum_subarray(&nums[j + 1..]);
                max_sum = max_sum.max(sum1 + sum2 + sum3);
            }
        }
        max_sum
    }
}

    The Rust details worth a closer look:

    • Slices of a vector. &nums[..i] is a &[i32] view of the first i elements. &nums[j + 1..] runs from j + 1 to the end. Neither copies any data, and an empty slice is allowed (but the helper would panic on it, which the loop bounds prevent).
    • Ranges exclude the end. 1..n stops at n - 1 and i..n - 1 stops at n - 2. If i equals n - 1, the range i..n - 1 is empty and the loop body never runs.
    • Associated functions. The helper has no self, so it is called as Solution::max_sum_subarray(...).
    • for &val in nums. Iterating a slice yields &i32, and the &val pattern copies each number out of its reference.
    • The 0i32 suffix. It fixes the type of sum2 to match the elements of nums.
    • max is a method. a.max(b) returns the larger of two integers.
    • Wrapping. With optimizations on, i32 overflow wraps silently, and the code assumes sums stay within the i32 range.

    Complexity

    Time: O(n³). The two loops visit about n² / 2 middle subarrays. Each visit calls the helper on a suffix, which costs up to O(n). The call on the prefix is made once per i, which adds only O(n²).

    Space: O(1). The slices are views, and the function keeps a few integers.

    Edge cases and common mistakes

    • All numbers negative. For [-1, -2, -3] the only choice is one element each, so the answer is -6. A 0 start for max_sum or for the helper's result would give a wrong, non-negative answer.
    • Exactly three numbers. The only loop pass is i = 1 with j = 1, and the result is the sum of all three.
    • Positive numbers only. For [1, 2, 3, 4] the answer is 10: the three subarrays together cover the whole vector.
    • Mixed signs. For [4, -1, 4, -1, 4] the answer is 12, three single 4s separated by the -1s.
    • Letting the middle reach the last element. If j could be n - 1, the third subarray would be empty and &nums[j + 1..] would be empty. The helper would then read nums[0] of an empty slice and panic.
    • Starting i at 0. The first subarray would be empty, and &nums[..0] would make the helper panic.
    • Declaring sum2 outside the outer loop. It would carry over from the previous start and the middle sums would be wrong.

    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