Start learning free

LESSON 219 OF 347 · PARTIAL SUMS #2

Max Sum of Three Subarrays in C#: Fixing the Middle, Kadane on the Sides

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 11
    Ctrl + Enter to check

    C# · PARTIAL SUMS #2

    Max Sum Of Three Subarrays in C#, explained

    Problem overview

    The method MaxSumOfThreeSubarrays receives an int[] nums with at least three numbers. It must pick three non-empty, non-overlapping subarrays so that the total of their sums is as large as possible, and return that total.

    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 and 9, so the answer is 28.

    Approach: loop over the middle subarray only

    The first lesson on this problem used six nested loops, one pair of indices per subarray, which costs O(n⁶). This lesson removes four of those loops.

    Fix the middle subarray, from index i to index j. The first subarray must lie somewhere inside nums[0..i - 1], and the third inside nums[j + 1..n - 1]. The two sides don't interact, so each can be chosen independently: for the left part, the best choice is the maximum subarray sum of that part, and for the right part, it is the maximum subarray sum of that part. The total for this middle is sum1 + sum2 + sum3, with sum2 the middle's own sum.

    Finding the maximum subarray sum of an array is a classic problem with a one-pass solution, Kadane's algorithm. It's wrapped in a helper, MaxSumSubarray, and called twice for every middle subarray. The loops over i and j are what remain.

    For the example, take the middle [7, -2, 9], indices 3 to 5. The left part is [2, 3, -8], whose best subarray sums to 5. The right part is [-9, 7, -2, 4], whose best subarray [7, -2, 4] sums to 9. With the middle's 14, the total is 5 + 14 + 9 = 28.

    Step by step

    1. Store the length in n.
    2. Start the answer at int.MinValue. The answer can be negative, so 0 is not a safe starting value.
    3. Choose where the middle starts. The loop variable i runs from 1, so the left part nums[0..i - 1] has at least one element. When i is n - 1, there's no room for the third subarray, but then the inner loop simply doesn't run.
    4. Best left subarray. Cut out nums[0..i - 1] and pass it to MaxSumSubarray, keeping the result in sum1. LINQ does the cutting: Skip drops elements from the front, Take keeps a given number, and ToArray converts the result back into an int[].
    5. Middle sum. Declare sum2 as 0 inside the outer loop, so it restarts for every i.
    6. Choose where the middle ends. The index j runs from i to n - 2, leaving at least one element for the third subarray.
    7. Grow the middle. Add nums[j] to sum2.
    8. Best right subarray. Use Skip(j + 1) to drop everything up to j, then call MaxSumSubarray and keep the result as sum3. Take stops when the sequence ends, so asking for more elements than remain is harmless.
    9. Update the answer with Math.Max(maxSum, sum1 + sum2 + sum3).
    10. Return maxSum after the outer loop.
    11. Write the helper. MaxSumSubarray keeps result, the best sum so far, starting at nums[0], and maxSum, the best sum of a subarray ending at the current element. For each val, maxSum becomes val + Math.Max(maxSum, 0): extend the previous subarray if its sum is positive, and start afresh at val otherwise. Then result is updated.

    The solution in C#

    class Solution {

    public int MaxSumSubarray(int[] nums) {
        int result = nums[0];
        int maxSum = 0;
        foreach (int val in nums) {
            maxSum = val + Math.Max(maxSum, 0);
            result = Math.Max(result, maxSum);
        }
        return result;
    }

    public int MaxSumOfThreeSubarrays(int[] nums) {
        int n = nums.Length;
        int maxSum = int.MinValue;
        for (int i = 1; i < n; i++) {
            int sum1 = this.MaxSumSubarray(nums.Skip(0).Take(i - 0).ToArray());
            int sum2 = 0;
            for (int j = i; j < n - 1; j++) {
                sum2 += nums[j];
                int sum3 = this.MaxSumSubarray(nums.Skip(j + 1).Take(nums.Length - j + 1).ToArray());
                maxSum = Math.Max(maxSum, sum1 + sum2 + sum3);
            }
        }
        return maxSum;
    }
}

    C# details worth noticing

    • LINQ. Skip, Take and ToArray are extension methods from the System.Linq namespace. They work on any sequence, and ToArray copies the selected elements into a new array. That copy is what makes this approach cost O(n) per call.
    • The two maxSum variables are separate. One is a local in MaxSumSubarray and the other is a local in MaxSumOfThreeSubarrays. Each method has its own scope.
    • this. is optional. MaxSumSubarray(...) alone calls the same method on the current object.
    • Safe over-taking. Take(count) returns fewer elements when the sequence is shorter, rather than throwing.

    Complexity

    Time: O(n³). The two loops visit about n²/2 pairs (i, j), and each pair builds arrays and runs Kadane's algorithm in O(n). That is a large improvement over O(n⁶). The helper calls repeat work, because the best left subarray for a given i is recomputed for every j, so later lessons can reduce the cost further by precomputing the best left and right values.

    Space: O(n) for the temporary arrays that ToArray creates.

    Edge cases and common mistakes

    • Empty sides. MaxSumSubarray starts from nums[0], so an empty array would throw. That's why i starts at 1 and j stops at n - 2, which keep both sides non-empty.
    • Exactly three numbers. Only i = 1 and j = 1 work, with one element in each part. For [5, -1, 5] the result is 9.
    • All negative numbers. The answer is the sum of three subarrays that are as small in magnitude as possible. For [-1, -2, -3, -4] it is -6, from -1, -2 and -3.
    • Starting Kadane's result at 0. This would claim an empty subarray with sum 0, which isn't allowed. The helper starts result at nums[0].
    • Forgetting to reset sum2. It's declared inside the outer loop, so every new start for the middle begins from 0.

    Testing

    • [2, 3, -8, 7, -2, 9, -9, 7, -2, 4] returns 28.
    • [5, -1, 5] returns 9.
    • [-1, -2, -3, -4] returns -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