Start learning free

LESSON 221 OF 348 · PARTIAL SUMS #2

Max Sum of Three Subarrays in TypeScript: O(n²) with Prefix Maxima

Practice O(n2) 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
    Ctrl + Enter to check

    TYPESCRIPT · PARTIAL SUMS #2

    Max Sum Of Three Subarrays in TypeScript, explained

    Problem overview

    The method maxSumOfThreeSubarrays takes an array nums with at least three integers and picks three non-empty subarrays that don't overlap and come one after another. It returns the largest possible sum of the three. Numbers can be negative, so the best answer may be negative too.

    For [2, 3, -8, 7, -2, 9, -9, 7, -2, 4] the best choice is [2, 3], [7, -2, 9] and [7, -2, 4], with sums 5, 14 and 9, for a total of 28.

    Approach: precompute the best left and right subarrays

    Fix the middle subarray by its first index i and last index j. The first subarray must fit inside nums[0..i - 1] and the third inside nums[j + 1..n - 1], and they can be chosen separately. The slow version of this idea computes the best subarray of each prefix and suffix again for every pair (i, j), which costs O(n³) in total.

    The same prefixes and suffixes come up over and over, so this lesson computes each answer once and stores it:

    • leftMaxSum[i] is the maximum subarray sum inside nums[0..i];
    • rightMaxSum[i] is the maximum subarray sum inside nums[i..n - 1].

    Both arrays are built in one pass each. The main search then reads from them in constant time, leaving two nested loops over the middle subarray: O(n²).

    For the example, the two arrays are:

    nums:        2  3  -8   7  -2   9  -9   7  -2   4
leftMaxSum:  2  5   5   7   7  14  14  14  14  14
rightMaxSum: 14 14 14  14   9   9   9   9   4   4

    With the middle subarray [7, -2, 9] (indices 3 to 5), the best left part is leftMaxSum[2], which is 5, and the best right part is rightMaxSum[6], which is 9. The total is 5 + 14 + 9 = 28.

    Step by step

    1. Store the length in n.
    2. Create leftMaxSum with new Array(n).fill(0). The constructor makes an array of n empty slots, and fill(0) puts a zero in each.
    3. Set leftMaxSum[0] to nums[0]. The only subarray of the first prefix is the first element.
    4. Start maxSum at nums[0]. It tracks the best sum of a subarray that ends at the current index.
    5. Loop i from 1 to n - 1.
    6. Update maxSum to nums[i] + Math.max(maxSum, 0). The best subarray ending at i extends the previous one only when that one has a positive sum; otherwise it starts fresh at nums[i].
    7. Set leftMaxSum[i] to the larger of leftMaxSum[i - 1] and maxSum. The best subarray inside nums[0..i] either ends at i or lies completely before it.
    8. Create rightMaxSum the same way as leftMaxSum.
    9. Set rightMaxSum[n - 1] to nums[n - 1]. The last suffix has one subarray only.
    10. Reuse maxSum, now holding the best sum of a subarray that starts at the current index. Start it at nums[n - 1].
    11. Loop i from n - 2 down to 0. The suffix at i depends on the one at i + 1, so the loop runs right to left.
    12. Update maxSum with the same formula, nums[i] + Math.max(maxSum, 0): extend the best subarray that starts at i + 1 if it is positive, or start fresh.
    13. Set rightMaxSum[i] to the larger of rightMaxSum[i + 1] and maxSum.
    14. Reset maxSum to Number.NEGATIVE_INFINITY for the answer. It is the best total found so far, and the answer can be negative, so it must start below any real total.
    15. Loop i from 1 to n - 1, the first index of the middle subarray. Starting at 1 leaves room for a non-empty first subarray.
    16. Read sum1 from leftMaxSum[i - 1], the best first subarray that ends before i.
    17. Start sum2 at 0. It will hold the middle subarray's sum.
    18. Loop j from i to n - 2, the last index of the middle subarray. The upper limit leaves one element for the third subarray.
    19. Add nums[j] to sum2.
    20. Read sum3 from rightMaxSum[j + 1], the best third subarray starting after j.
    21. Update maxSum with sum1 + sum2 + sum3 if it is larger.
    22. Return maxSum.

    The solution in TypeScript

    class Solution {

    maxSumOfThreeSubarrays(nums: number[]): number {
        let n = nums.length;

        let leftMaxSum: number[] = new Array(n).fill(0);
        leftMaxSum[0] = nums[0];
        let maxSum = nums[0];
        for (let i = 1; i < n; ++i) {
            maxSum = nums[i] + Math.max(maxSum, 0);
            leftMaxSum[i] = Math.max(leftMaxSum[i - 1], maxSum);
        }

        let rightMaxSum: number[] = new Array(n).fill(0);
        rightMaxSum[n - 1] = nums[n - 1];
        maxSum = nums[n - 1];
        for (let i = n - 2; i >= 0; --i) {
            maxSum = nums[i] + Math.max(maxSum, 0);
            rightMaxSum[i] = Math.max(rightMaxSum[i + 1], maxSum);
        }

        maxSum = Number.NEGATIVE_INFINITY;
        for (let i = 1; i < n; ++i) {
            let sum1 = leftMaxSum[i - 1];
            let sum2 = 0;
            for (let j = i; j < n - 1; ++j) {
                sum2 += nums[j];
                let sum3 = rightMaxSum[j + 1];
                maxSum = Math.max(maxSum, sum1 + sum2 + sum3);
            }
        }

        return maxSum;
    }
}

    The TypeScript details worth knowing:

    • Creating a filled array. new Array(n) with a single number argument makes an array of that length with empty slots, and .fill(0) turns them into zeros. The annotation number[] tells the compiler what the array will hold; it has no effect at run time.
    • One variable, two jobs. maxSum is reassigned three times: for the best subarray ending at the current index, then starting at it, then for the final answer. Because it is declared with let and has type number from its first value, all three uses are allowed.
    • Prefix and suffix versions of the same formula. Both passes use nums[i] + Math.max(maxSum, 0). Only the direction changes.
    • Doubles, not integers. Sums are plain number values, so there is no overflow to worry about for ordinary inputs; integers stay exact up to 2^53.

    Complexity

    Time: O(n²). Building each of the two arrays is a single pass, O(n). The final nested loops try about n²/2 pairs (i, j) and spend constant time on each one, because the left and right bests are plain array reads.

    Space: O(n). The two arrays hold n numbers each.

    Edge cases and common mistakes

    • Negative totals. For [-5, -1, -3, -2] the answer is -6. Initializing the answer with 0 would return 0, which is not the sum of any three subarrays.
    • Minimum size. For [1, 2, 3] the only valid choice is three single elements, and the code returns 6.
    • Starting a maximum at 0. leftMaxSum[0] and the first maxSum start at nums[0] because an array of negative values has no non-negative subarray sum.
    • Off-by-one on the sides. The first subarray ends before i, so it reads leftMaxSum[i - 1]. The third starts after j, so it reads rightMaxSum[j + 1]. Using leftMaxSum[i] would let the first subarray overlap the middle one.
    • Treating the arrays as exact-length bests. leftMaxSum[i] is the best sum anywhere inside the prefix, not the best sum of a subarray ending at i. The running maxSum holds the latter.

    Testing

    • [2, 3, -8, 7, -2, 9, -9, 7, -2, 4] gives 28.
    • [-5, -1, -3, -2] gives -6.
    • [1, 2, 3] gives 6.
    • [-1, -2, -3] gives -6.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free