LESSON 221 OF 347 · PARTIAL SUMS #2

Max Sum of Three Subarrays in C#: O(n) with a Running Difference

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

C# · PARTIAL SUMS #2

Max Sum Of Three Subarrays in C#, explained

Problem overview

MaxSumOfThreeSubarrays takes an int[] nums with at least three elements and returns the largest total of three non-empty, non-overlapping subarrays. They stay in left-to-right order, and gaps are allowed. For [2, 3, -8, 7, -2, 9, -9, 7, -2, 4] the answer is 28, from [2, 3], [7, -2, 9] and [7, -2, 4].

Values may be negative, so the answer can be negative: [-1, -2, -3] gives -6.

Approach

The idea is to fix the middle subarray and read the best first and third subarrays from tables. leftMaxSum[i] is the best subarray sum inside nums[0..i], and rightMaxSum[i] is the best inside nums[i..n - 1]. Both take one pass each, using the rule "extend the previous subarray only if its sum is positive".

The earlier version of this lesson tries every start and end of the middle subarray, which costs O(n²). This version loops over the end of the middle subarray only, and gets the best start in constant time with a running maximum.

Why a difference works

Let P(i) be the sum of nums[0..i]. A middle subarray that starts at k and ends at i has sum P(i) - P(k - 1). The total for that choice is

leftMaxSum[k - 1] + (P(i) - P(k - 1)) + rightMaxSum[i + 1]
= P(i) + (leftMaxSum[k - 1] - P(k - 1)) + rightMaxSum[i + 1]

Only the middle term depends on k, and it doesn't depend on i. So for a fixed end i, the best start is the k that maximizes leftMaxSum[k - 1] - P(k - 1) among all starts up to i. As i moves right, one new start becomes available, so keep a running maximum, maxDiff.

Step by step

Build leftMaxSum and rightMaxSum exactly as in the previous version: a forward pass and a backward pass, each tracking the best subarray ending (or starting) at the current index in maxSum.
Reuse maxSum for the answer and set it to int.MinValue, because the answer may be negative.
Create partialSum with nums[0]. At the top of each iteration of the main loop it holds the sum of nums[0..i - 1].
Create maxDiff with int.MinValue, since the first real value is only known inside the loop.
Loop i from 1 to n - 2, the possible last elements of the middle subarray. It needs a first subarray before it and a third after it.
Add the new start first. Starting the middle subarray at i contributes leftMaxSum[i - 1] - partialSum, and partialSum is still the sum up to i - 1, which is what that formula needs.
Then extend partialSum with nums[i], so it is P(i).
Combine partialSum + rightMaxSum[i + 1] + maxDiff into maxSum and return it after the loop.

The order inside the loop matters. Updating maxDiff before adding nums[i] allows a middle subarray of length one (start and end both at i). Doing it after would use the wrong prefix sum.

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;
        int partialSum = nums[0];
        int maxDiff = int.MinValue;
        for (int i = 1; i < n - 1; ++i) {
            maxDiff = Math.Max(leftMaxSum[i - 1] - partialSum, maxDiff);
            partialSum += nums[i];
            maxSum = Math.Max(partialSum + rightMaxSum[i + 1] + maxDiff, maxSum);
        }

        return maxSum;
    }
};

C# details:

int.MinValue as a placeholder. It is safe here only because maxDiff is overwritten by the Math.Max on the first iteration before it is added to anything. Adding to int.MinValue would wrap around silently, since C# doesn't check int overflow by default.
Math.Max lives in System and has an overload for each numeric type. With int arguments, it returns an int.
Arrays start zeroed. new int[n] fills every cell with 0, so the two tables are ready to be overwritten.

Tracing the example

At i = 3 in the example, partialSum before the update is -3 and leftMaxSum[2] is 5, so the candidate is 5 - (-3) = 8. That is the start of [7, ...] after [2, 3]. At i = 5, partialSum is 11, rightMaxSum[6] is 9 and maxDiff is 8, so the total is 11 + 9 + 8 = 28.

Running the code on the example, maxDiff takes the values 0, 0, 8, 8, 8, 8, 12, 12 for i from 1 to 8. It jumps to 12 at i = 7: leftMaxSum[6] is 14 and partialSum is 2, so starting the middle subarray at index 7 is worth 14 - 2 = 12. The candidate for that i is only 9 + 4 + 12 = 25, though. The best total, 28, comes from i = 5, which shows that the maximum is taken over all ends, not just the last one.

Conceptually the optimization is a standard trick: when a double loop has a term that depends only on the inner index, replace the inner loop with a running maximum of that term. It works here because the term, leftMaxSum[k - 1] - P(k - 1), can be computed from the left alone.

Complexity

Time: O(n). There are three passes over the array, each doing constant work per element. No nested loops remain.

Space: O(n). The two tables take n integers each. The running values add only constant space.

Edge cases and common mistakes

Exactly three elements. The loop runs once, with i = 1. It returns nums[0] + nums[1] + nums[2], which is the only possible choice.
All negative numbers. [-1, -2, -3, -4] gives -6. A starting value of 0 for the answer would give a wrong result.
Looping to n - 1. Then rightMaxSum[i + 1] is out of range and throws IndexOutOfRangeException.
Swapping the two update lines. If partialSum is updated before maxDiff, the difference subtracts the wrong prefix sum.
Forgetting that the left table is a maximum. leftMaxSum[k - 1] may come from a subarray that ends well before k - 1. That is allowed, because gaps are fine.

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