Start learning free

LESSON 210 OF 348 · PARTIAL SUMS #1

Maximum Sum Subarray in TypeScript: Prefix Sums in O(n)

Practice O(n) Read the full explanation

( Prefix Sums Approach )


Given an input array that may contain both positive and negative integers, find the sum of continuous subarray of numbers which has the largest sum.

Example:

Input: nums = [-2, -5, 6, -2, -3, 1, 5, -6]
Output: 7
Explanation: sum([6, -2, -3, 1, 5]) = 7

Note:

Your algorithm should run in O(n) time and use at most O(n) extra space.


STEP 1 OF 7
    Ctrl + Enter to check

    TYPESCRIPT · PARTIAL SUMS #1

    Maximum Sum Subarray in TypeScript, explained

    Problem overview

    The method maxSumSubarray receives an array nums of integers that may be positive, negative or both. It returns the largest sum that any continuous run of elements (a subarray) can have. The run must contain at least one element.

    For nums = [-2, -5, 6, -2, -3, 1, 5, -6] the best run is [6, -2, -3, 1, 5], which sums to 7, so the answer is 7. The statement asks for O(n) time, so a single pass over the array has to be enough.

    Approach: best sum ending here, from prefix sums

    The slow way tries every start and every end and adds up each run, which costs O(n²) with running sums or O(n³) without. This lesson gets to O(n) with prefix sums.

    Let the prefix sum at position i be the sum of all elements from index 0 up to i. The sum of a run that starts at index a and ends at i is the prefix sum at i minus the prefix sum just before a. The subtracted prefix can also be the empty prefix, whose sum is 0, which covers runs that start at index 0.

    Now fix the end i and ask for the best run that ends there. The prefix sum at i is a fixed number, so the run is largest when the subtracted prefix is smallest. The smallest earlier prefix sum is all we need to remember, and we can update it as we move right. That turns "try every start" into one subtraction.

    On the example, the prefix sums are -2, -7, -1, -3, -6, -5, 0, -6. The smallest prefix before the element 5 (prefix sum 0) is -7, and 0 - (-7) = 7. That difference is the run starting right after the prefix -7, which is the run [6, -2, -3, 1, 5].

    Step by step

    1. Keep a running prefix sum and the smallest one seen. partialSum and minSum both start at 0, because the empty prefix is allowed as a starting point.
    2. Start the answer from a real subarray sum. The array can be all negative, in which case the answer is negative too, so starting result at 0 would report a sum no subarray has. The single element nums[0] is a valid subarray, so it is a safe start.
    3. Loop over the elements with a variable val.
    4. Add the element to partialSum, so it covers everything up to and including the current element.
    5. Update result. The best run ending at this element has sum partialSum - minSum. Keep the larger of that and the previous best, using Math.max.
    6. Update minSum with Math.min so that later elements can start a run after this prefix. This comes after step 5 on purpose: a run must contain at least one element, so the current prefix must not be subtracted from itself.
    7. Return result once the loop is done.

    The solution in TypeScript

    class Solution {
    maxSumSubarray(nums: number[]): number {
        let partialSum = 0, minSum = 0;
        let result = nums[0];
        for (const val of nums) {
            partialSum += val;
            result = Math.max(result, partialSum - minSum);
            minSum = Math.min(minSum, partialSum);
        }
        return result;
    }
}

    Tracing the example, the loop shows how the three variables move (values after each element):

    val  partialSum  minSum  result
 -2          -2      -2      -2
 -5          -7      -7      -2
  6          -1      -7       6
 -2          -3      -7       6
 -3          -6      -7       6
  1          -5      -7       6
  5           0      -7       7
 -6          -6      -7       7

    Some TypeScript details:

    • Inferred types. let partialSum = 0, minSum = 0; declares two variables in one statement, and TypeScript infers number for both from the initial values. No annotation is needed.
    • for...of gives values. for (const val of nums) visits the elements themselves. for (const i in nums) would give the indices as strings, which is a different loop.
    • Types are erased. The number[] annotation checks the call at compile time only. At run time the method only sees whatever array it receives.
    • An empty array. With nums = [], nums[0] is undefined and the method returns undefined, although the signature says number. The lesson's inputs always have at least one element, but a guard such as if (nums.length === 0) return 0; is worth adding in real code.

    Complexity

    Time: O(n). The loop visits each element once and does a constant amount of work for each.

    Space: O(1). The method keeps three numbers. The statement allows O(n) extra space, and this solution needs none, because it never stores the whole array of prefix sums: only the running one and the minimum matter.

    Edge cases and common mistakes

    • All negative numbers. [-4, -1, -7] returns -1, the single best element. Starting result at 0 would wrongly return 0.
    • A single element. [5] returns 5.
    • A dip between two good runs. [3, -10, 4] returns 4, because joining the runs through -10 is worse than taking 4 alone. The minimum prefix, -7, is subtracted from the prefix -3 to leave exactly the 4.
    • Updating minSum too early. If minSum is updated before result, then partialSum - minSum can be 0 for an empty run, and an all-negative array gives 0 again.
    • Forgetting the empty prefix. Starting minSum at a large number instead of 0 would miss every run that begins at index 0.

    Testing

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