Start learning free

LESSON 208 OF 348 · FREE CODING INTERVIEW QUESTIONS

Maximum Sum Subarray in TypeScript: O(n^2) with a Running Sum

Practice O(n2) Read the full explanation

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^2) time and use O(1) extra space.




Let's come up with a brute force approach. Brute force tries each and every candidate to our solution. For this problem, the candidates are all the subarrays of nums. How can we try out each subarray?

A subarray is defined by its left endpoint, let's name it index i and its right point, let's name it index j. We should go through each pair of indices (i, j) such that 0 <= i <= j < n. How can we achieve this?

Using two nested for loops! The first loop will try out each possible i between 0 and n - 1. The second loop will be written inside the first one and will try out each possible j between i and n - 1. 
for each i : 0 -> n - 1:
		for each j : i -> n - 1:
We will use a variable maxSum to store the greatest sum found so far and for each pair (i, j), update maxSum with sum(nums[i...j]) if it's the case: 
maxSum = nums[0]
for each i : 0 -> n - 1:
	for each j : i -> n - 1:
		maxSum = max(maxSum, sum(nums[i...j]))
return maxSum
All we have to do now is find a way of getting sum(nums[i...j]) in O(1) time. How can we do this?

One way is using Partial Sums. But that implies using an extra array which gives extra space of O(n). There is a better way. We can use a variable sum to store the sum of the current subarray sum(nums[i...j]). 
maxSum = nums[0]
for each i : 0 -> n - 1:
	for each j : i -> n - 1:
		maxSum = max(maxSum, sum)
return maxSum
How should we update this variable throught the algorithm to make sure that it always stores the correct sum?

Each time we increment j in the second loop, we should add nums[j] to sum. Also, each time we increment i in the first loop, we start with a new empty subarray so we should reset sum to 0: 
maxSum = nums[0]
for each i : 0 -> n - 1:
	sum = 0
	for each j : i -> n - 1:
		sum += nums[j]
		maxSum = max(maxSum, sum)
return maxSum

STEP 1 OF 7
    Ctrl + Enter to check

    TYPESCRIPT · FREE CODING INTERVIEW QUESTIONS

    Maximum Sum Subarray in TypeScript, explained

    Problem overview

    The method maxSumSubarray receives an array of integers, nums, which may contain negative values. It returns the largest sum that any continuous subarray can have. A subarray is a run of neighbouring elements, from some index i to some index j, with i <= j. It must contain at least one element.

    For nums = [-2, -5, 6, -2, -3, 1, 5, -6] the best subarray is [6, -2, -3, 1, 5], whose sum is 7. No other run of neighbours does better.

    The statement allows O(n^2) time and O(1) extra space. That is the budget of a brute-force search over all subarrays, as long as each one is evaluated cheaply and no extra array is built.

    Approach: try every subarray with a running sum

    A subarray is defined by its two ends, so trying every subarray means trying every pair (i, j) with 0 <= i <= j < n. Two nested loops do that: the outer one picks the left end i, and the inner one picks the right end j, from i to the end of the array.

    For each pair, we need the sum of nums[i..j]. Adding up the elements from scratch each time would cost another loop and make the whole thing O(n^3). Prefix sums would fix that, but they need an extra array of size n. There is a cheaper way that uses neither.

    For a fixed i, moving j one step to the right just appends one element to the subarray. So keep a variable sum for the current subarray: set it to 0 when i changes, and add nums[j] each time j advances. Every pair then costs O(1), and the extra space is a couple of variables.

    Alongside it, keep maxSum, the best sum seen so far, and update it after each addition.

    For [3, -4, 2]: with i = 0 the running sums are 3, -1 and 1. With i = 1 they are -4 and -2. With i = 2 the only sum is 2. The largest of all of them is 3.

    Step by step

    1. Declare maxSum and initialize it to nums[0]. The answer can be negative, so starting at 0 would be a trap: for [-4, -1, -8] it would report 0, which is not the sum of any subarray. nums[0] is itself a subarray, so it is a safe starting value.
    2. Loop with i over every possible first index, from 0 to nums.length - 1.
    3. Declare sum inside that loop and set it to 0. Declaring it there gives each start index a fresh, empty subarray, and the variable is not needed outside.
    4. Loop with j over every possible last index, from i to nums.length - 1. This loop sits inside the first one. Starting at i means the shortest subarray has one element.
    5. Add nums[j] to sum. This extends the previous subarray by one element, so sum now equals the sum of nums[i..j].
    6. Update maxSum in one line with Math.max(maxSum, sum), which keeps the larger of the two.
    7. Return maxSum once both loops have finished, meaning every pair of indices has been tried.

    The solution in TypeScript

    class Solution {

    maxSumSubarray(nums: number[]): number {
        let maxSum = nums[0];
        for (let i = 0; i < nums.length; ++i) {
            let sum = 0;
            for (let j = i; j < nums.length; ++j) {
                sum += nums[j];
                maxSum = Math.max(maxSum, sum);
            }
        }
        return maxSum;
    }
}

    TypeScript details worth a look:

    • Everything is inferred. maxSum gets the type number from nums[0], and sum from the literal 0. Only the parameter and return types are written out.
    • let is block scoped. The sum declared inside the outer loop exists only for that iteration, which is what makes the reset automatic.
    • Math.max takes any number of arguments. Here it takes two and returns the larger one.
    • Numbers are doubles. Sums of ordinary integers are exact. Integers only start losing precision beyond 2^53, and there is no integer overflow as in some other languages.

    Complexity

    Time: O(n^2). For each i, the inner loop runs n - i times, so the total is n + (n - 1) + ... + 1, which is n(n + 1) / 2. The body does constant work.

    Space: O(1). Only maxSum, sum, i and j are stored.

    This is the brute-force baseline. Later lessons on the same problem improve the running time.

    Edge cases and common mistakes

    • All numbers negative. For [-4, -1, -8] the answer is -1, the best single element. This is why maxSum starts at nums[0] rather than 0.
    • A single element. For [5] both loops run once and the answer is 5.
    • Declaring sum outside the outer loop. Without the reset, the sum from the previous start index carries over, and subarrays are no longer measured from i.
    • Starting j at 0. Then j can be smaller than i, and the loop adds elements that are not part of any subarray starting at i.
    • Allowing an empty subarray. The answer must be a real subarray, so the empty sum of 0 is not a candidate.
    • An empty array. nums[0] is undefined, the loops never run, and the method returns undefined even though its type says number. The compiled code has no check for it, so a real program would test nums.length first.

    Testing

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