LESSON 220 OF 347 · PARTIAL SUMS #2

Max Sum of Three Subarrays in C#: 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

C# · PARTIAL SUMS #2

Max Sum Of Three Subarrays in C#, explained

Problem overview

MaxSumOfThreeSubarrays receives an int[] nums with at least three elements and returns the largest total you can get from three non-empty subarrays that don't overlap. The subarrays are contiguous, they keep their left-to-right order, and gaps between them are allowed.

For [2, 3, -8, 7, -2, 9, -9, 7, -2, 4] the best choice is [2, 3], [7, -2, 9] and [7, -2, 4], worth 5 + 14 + 9 = 28. The -8 and -9 are skipped in the gaps. The numbers can be negative, so the answer can be negative too: for [-1, -2, -3] each element must be its own subarray, and the answer is -6.

Approach

Fix the middle subarray. Once you know where it starts and ends, the first subarray must lie entirely to its left and the third entirely to its right. Each side is independent, so you only need the best single subarray in a prefix and in a suffix. Both can be precomputed once:

leftMaxSum[i]: the best subarray sum inside nums[0..i].
rightMaxSum[i]: the best subarray sum inside nums[i..n - 1].

Then try every middle subarray and add the left best before it, the middle sum and the right best after it. Trying all middles is two nested loops, so this lesson runs in O(n²). The next lesson on this problem removes the inner loop.

Best subarray ending at each index

To fill leftMaxSum you need the best subarray that ends at index i. It either extends the best one ending at i - 1 or starts fresh at i. Extending only helps when the previous sum is positive, which gives nums[i] + Math.Max(maxSum, 0). This is Kadane's algorithm. The prefix best is then the larger of the previous prefix best and the subarray ending at i.

On the example, leftMaxSum comes out as 2, 5, 5, 7, 7, 14, 14, 14, 14, 14 and rightMaxSum as 14, 14, 14, 14, 9, 9, 9, 9, 4, 4. The code below computes both arrays for this example.

Step by step

Store the length in n, since it's used constantly.
Create leftMaxSum. A new int[] starts filled with zeros, and every cell gets overwritten.
Seed index 0 with nums[0], the only subarray of a one-element prefix. Start maxSum at the same value.
Loop from 1 to n - 1. Update maxSum (best subarray ending here), then leftMaxSum[i].
Mirror it for rightMaxSum. Seed the last index, then loop from n - 2 down to 0. Now maxSum means the best subarray starting at i.
Reset maxSum to int.MinValue to hold the final answer. Zero would be wrong, because the answer can be negative.
Loop over the start i of the middle subarray from 1, so the first subarray is not empty. Read sum1 = leftMaxSum[i - 1] and set sum2 to 0.
Loop over the end j of the middle subarray from i up to n - 2, so a third subarray still fits. Add nums[j] to sum2 and read sum3 = rightMaxSum[j + 1].
Keep the best of sum1 + sum2 + sum3 and return it.

The solution in C#

class Solution {

    public int MaxSumOfThreeSubarrays(int[] nums) {
        int n = nums.Length;

        int[] leftMaxSum = new int[n];
        leftMaxSum[0] = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < n; ++i) {
            maxSum = nums[i] + Math.Max(maxSum, 0);
            leftMaxSum[i] = Math.Max(leftMaxSum[i - 1], maxSum);
        }

        int[] rightMaxSum = new int[n];
        rightMaxSum[n - 1] = nums[n - 1];
        maxSum = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            maxSum = nums[i] + Math.Max(maxSum, 0);
            rightMaxSum[i] = Math.Max(rightMaxSum[i + 1], maxSum);
        }

        maxSum = int.MinValue;
        for (int i = 1; i < n; ++i) {
            int sum1 = leftMaxSum[i - 1];
            int sum2 = 0;
            for (int j = i; j < n - 1; ++j) {
                sum2 += nums[j];
                int sum3 = rightMaxSum[j + 1];
                maxSum = Math.Max(maxSum, sum1 + sum2 + sum3);
            }
        }

        return maxSum;
    }
};

C# details worth noting:

Reusing maxSum. The same variable plays three roles: the best sum ending at the current index, then the best starting at it, then the final answer. Each role begins with an assignment, so nothing leaks between them.
++i and --i. In a for update they behave exactly like i++ and i--, because the value of the expression isn't used.
int.MinValue. It is the smallest int, -2,147,483,648, and works as a "no answer yet" value. Adding to it would wrap around silently, but the code only compares it, and every candidate is far above it.
Arithmetic doesn't check overflow. By default C# int sums wrap around without an error. The lesson's inputs are small, but very large values could overflow sum1 + sum2 + sum3.
The trailing semicolon after the class's closing brace is allowed in C# and does nothing.

Complexity

Time: O(n²). The two precomputing loops are O(n). The nested loops visit each pair (i, j) with i <= j, about n²/2 of them, and each does constant work.

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

Edge cases and common mistakes

Initializing the answer with 0. This returns 0 for [-1, -2, -3] instead of -6. Start from int.MinValue.
Letting a negative running sum carry on. Without the Math.Max(maxSum, 0) part, a negative prefix would be dragged into every later subarray.
Exactly three elements. Each element is its own subarray. The loop runs with i = 1, j = 1, and the answer is nums[0] + nums[1] + nums[2].
Letting j reach n - 1. Then rightMaxSum[j + 1] reads past the end and throws IndexOutOfRangeException.
Using the prefix best as an exact sum. leftMaxSum[i] is a maximum over the whole prefix, so the first subarray doesn't have to end at index i. That is what allows gaps.

Testing

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

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

Start learning free