Start learning free

LESSON 209 OF 348 · PARTIAL SUMS #1

Maximum Sum Subarray in TypeScript: Kadane's Algorithm in O(n)

Practice O(n) Read the full explanation

( Kadane's Algorithm )


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 O(1) extra space.


STEP 1 OF 6
    Ctrl + Enter to check

    TYPESCRIPT · PARTIAL SUMS #1

    Maximum Sum Subarray in TypeScript, explained

    Problem overview

    The method maxSumSubarray receives an array of integers, nums, which may include negative values. It returns the largest sum of any continuous subarray: a block of neighbouring elements, with at least one element.

    In the example, [-2, -5, 6, -2, -3, 1, 5, -6], the best block is [6, -2, -3, 1, 5], with sum 7. The statement asks for O(n) time and O(1) extra space. This technique is known as Kadane's algorithm.

    Approach: the best sum ending at each element

    Checking every subarray works but takes O(n²) or O(n³) time. The faster idea is to ask a smaller question at each position: what is the largest sum of a subarray that ends at this element? Call it maxSum. The overall answer is the largest maxSum over all positions, since the best subarray has to end somewhere.

    The recurrence is short. A subarray ending at the current element val either extends the best subarray ending at the previous element, or starts fresh at val. Extending only helps when the previous best sum is positive; if it is negative, carrying it along makes things worse. So:

    maxSum = val + max(previous maxSum, 0)

    Trace the example. The values of maxSum after each element are -2, -5, 6, 4, 1, 2, 7 and 1. At -5, the previous sum is negative, so the block restarts. At 6 it restarts again. Then it carries on: 6 - 2 = 4, 4 - 3 = 1, 1 + 1 = 2, 2 + 5 = 7. The largest value seen is 7.

    Step by step

    1. Initialize result with nums[0]. The answer can be negative, so starting at 0 would be wrong: for [-3, -1, -2] it would report 0, which isn't the sum of any subarray. nums[0] is a subarray by itself, so it is a safe starting point.
    2. Start maxSum at 0. Before any element there is an empty prefix, and the formula val + Math.max(maxSum, 0) treats 0 and "no previous block" the same way.
    3. Loop over the elements with a variable val.
    4. Update maxSum with the recurrence val + Math.max(maxSum, 0): extend the previous block, or start a new one if that block's sum is negative.
    5. Update result with Math.max(result, maxSum), in case this block is the best so far.
    6. Return result once the loop is done.

    The solution in TypeScript

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

    Details worth knowing:

    • for (let val of nums) loops over the values, not the indices. const val would also work, since val is never reassigned inside the loop.
    • Math.max accepts any number of arguments and returns the largest. Here it makes the "extend or restart" choice without an if.
    • No overflow. TypeScript's number is a double. Sums stay exact up to 2^53, and nothing wraps around the way a 32-bit integer would in some other languages.
    • Types are erased. The annotations number[] and number are checked by the compiler only; nothing verifies them when the JavaScript runs.
    • The input is not changed, unlike in the sorting lessons. The loop only reads nums.

    Complexity

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

    Space: O(1). The code needs only result and maxSum, no matter how long the array is.

    Edge cases and common mistakes

    • All negative numbers. [-3, -1, -2] returns -1: the best subarray is the single element -1. Initializing result with 0 would wrongly return 0.
    • A single element. [4] returns 4.
    • All positive numbers. [1, 2, 3] returns 6, the whole array.
    • An empty array. The statement doesn't allow it. The code would return undefined, because nums[0] doesn't exist, even though the declared type is number.
    • Confusing subarrays with subsequences. A subarray must be contiguous, so skipping the negative values in the middle isn't allowed. That's why [6, -2, -3, 1, 5] is counted whole in the example.
    • Updating result before maxSum. Then result would use the previous element's sum, and the final element would be missed.

    Testing

    • [-2, -5, 6, -2, -3, 1, 5, -6] gives 7.
    • [-3, -1, -2] gives -1.
    • [4] gives 4.
    • [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