Start learning free

LESSON 222 OF 348 · PARTIAL SUMS #2

Max Sum of Three Subarrays in TypeScript: O(n) with a Running Maximum

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

    TYPESCRIPT · PARTIAL SUMS #2

    Max Sum Of Three Subarrays in TypeScript, explained

    Problem overview

    The method maxSumOfThreeSubarrays receives an array nums of at least three integers. It must choose three non-empty subarrays that don't overlap and appear in order, and return the largest possible sum of the three. Values may be negative.

    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].

    Approach: remove the loop over the middle subarray's start

    The previous idea fixes the middle subarray by its first index and last index. The best first subarray then comes from an array of prefix maxima, and the best third from an array of suffix maxima, so each pair of boundaries costs constant time. Two nested loops still try every pair, which takes O(n²).

    This lesson keeps the last index of the middle subarray as the only loop and drops the loop over its start. Write P[k] for the sum of nums[0..k - 1], so P[0] is 0. If the middle subarray starts at k and ends at i, its sum is P[i + 1] - P[k]. The total for that choice is

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

    Group the parts that depend on k: (leftMaxSum[k - 1] - P[k]). For a fixed i, the best start k is the one that makes this part largest, among the starts 1 to i. That maximum is maxDiff, and it can be kept as a running maximum while i moves right: each new i adds one more possible start and nothing else changes.

    In the example, the best total is found at i = 5. The best start up to then is k = 3, where leftMaxSum[2] - P[3] is 5 - (-3) = 8. Then P[6] is 11, rightMaxSum[6] is 9, and 11 + 8 + 9 = 28.

    Step by step

    1. Store the length in n, typed as number.
    2. Create leftMaxSum as an array of n zeros. Entry i will hold the best subarray sum inside nums[0..i].
    3. Set leftMaxSum[0] to nums[0]. The first prefix has one subarray only.
    4. Start maxSum at nums[0], the best sum of a subarray ending at the current index.
    5. Loop i from 1 to n - 1.
    6. Update maxSum to nums[i] + Math.max(maxSum, 0): extend the earlier subarray if its sum is positive, otherwise start at nums[i].
    7. Set leftMaxSum[i] to the larger of leftMaxSum[i - 1] and maxSum. The best subarray inside the prefix either ends at i or lies before it.
    8. Create rightMaxSum as another array of zeros.
    9. Set rightMaxSum[n - 1] to nums[n - 1].
    10. Reuse maxSum, now for the best subarray starting at the current index, beginning with nums[n - 1].
    11. Loop i from n - 2 down to 0.
    12. Update maxSum with the same formula as before, nums[i] + Math.max(maxSum, 0), this time extending the subarray that starts at i + 1.
    13. Set rightMaxSum[i] to the larger of rightMaxSum[i + 1] and maxSum.
    14. Reset maxSum to Number.NEGATIVE_INFINITY to hold the answer. The answer can be negative, so it must start below every real total.
    15. Create partialSum starting at nums[0]. At the start of each iteration below it equals P[i], the sum of nums[0..i - 1].
    16. Create maxDiff starting at Number.NEGATIVE_INFINITY. It is the largest value of leftMaxSum[k - 1] - P[k] seen so far.
    17. Loop i from 1 to n - 2, the last index of the middle subarray. It needs a non-empty subarray before it and after it.
    18. Update maxDiff with leftMaxSum[i - 1] - partialSum. That adds k = i as a possible start. It happens before partialSum changes, while partialSum is still P[i].
    19. Add nums[i] to partialSum, which now equals P[i + 1].
    20. Update maxSum with partialSum + rightMaxSum[i + 1] + maxDiff, the best first subarray, plus the middle one ending at i, plus the best third.
    21. Return maxSum.

    The solution in TypeScript

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

        let leftMaxSum: number[] = new Array(n).fill(0);
        leftMaxSum[0] = nums[0];
        let maxSum: number = 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;
        let partialSum: number = nums[0];
        let maxDiff: number = Number.NEGATIVE_INFINITY;
        for (let 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;
    }
}

    The TypeScript details worth knowing:

    • Annotations are optional here. let n: number = nums.length says what the compiler would already infer. The annotations are erased when TypeScript compiles to JavaScript, so they document the code and catch mistakes at compile time, and they do nothing at run time.
    • Number.NEGATIVE_INFINITY as a start value. Any real number is larger than it, so the first Math.max replaces it. Starting maxDiff at 0 would be wrong, because the difference leftMaxSum[k - 1] - P[k] can be negative for every start.
    • Order inside the loop. The three statements must stay in order. Updating maxDiff uses partialSum before nums[i] is added; the last line uses it after.
    • Numbers are doubles. Differences and sums of ordinary inputs are exact, and there is no integer overflow to handle.

    Complexity

    Time: O(n). There are three loops, each running at most n times with constant work in the body.

    Space: O(n). The two arrays leftMaxSum and rightMaxSum hold n numbers each. The remaining variables are single numbers.

    Edge cases and common mistakes

    • Exactly three elements. For [1, 2, 3] the loop runs once, with i = 1, and returns 6.
    • All negative. For [-1, -2, -3] the answer is -6. A starting value of 0 for maxSum or maxDiff would hide it.
    • Wrong loop range. Running i up to n - 1 would read rightMaxSum[n], which is undefined in JavaScript, and the arithmetic would produce NaN.
    • Updating partialSum too early. If nums[i] were added before maxDiff is updated, the difference would subtract P[i + 1] instead of P[i], and the middle subarray would lose its first element.
    • Middle subarray of one element. The start k may equal i, because maxDiff is updated with the current i before it is used. Updating it after the last line would force the middle subarray to have at least two elements.

    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