Find the largest sum of contiguous subarray

Learn how to write an algorithm to find the largest sum of contiguous subarray from the given array.

Example

Input:
[-2, -3, 4, -1, -2, 1, 5, -3]

Output:
7

The subarray from index 2 to 6 has the largest sum 4 + -1 + -2 + 1 + 5 = 7.

One way to solve this problem is to find all the subarray and then sum each element of it and store the maximum of them which will work in O(n ^ 2).

There is another efficient algorithm known as kadane’s algorithm which works in O(n).

Kadane’s algorithm to find the largest sum contiguous subarray

Conceptually it works as follows

• Use two variables to track the current sum and max sum.
• Keep adding the elements of the array to the current sum and check if it is greater than max sum then update the max sum to current sum.
• After each addition if current sum is less than 0 then reset it to 0.

Kadane’s algorithm expects that there is at-least one positive value should be present in the array other wise it will return 0.

const largestSum = (arr) => {
    //Track the curent and total sum
    let max_so_far = Number.MIN_SAFE_INTEGER;
    let max_current = 0;

    for (let i = 0; i < arr.length; i++) {
        //Add the value to current sum
        max_current += arr[i];

        //Update the max sum
        max_so_far = Math.max(max_so_far, max_current);

        //If current sum < 0 then reset it to 0
        if (max_current < 0) {
          max_current = 0;
        }
    }

    //return max sum
    return max_so_far;
};

Input:
console.log(largestSum([-2, -3, 4, -1, -2, 1, 5, -3]));

Output:
7

Time complexity: O(n).
Space complexity: O(1).

---

Kadane's algorithm with all negative numbers in the array.

As the above algorithm only works when there is at-least one positive value is present, we can modify it little to make it work with all negative values in O(n).

We use the following approach, rather than resetting the current sum to 0 if it is negative we get the max of current sum and current value of array and then store max of them and return it at the end.

const largestSum = (arr) => {
    //Track the curent and total sum
    let max_so_far = Number.MIN_SAFE_INTEGER;
    let max_current = 0;

    for (let i = 0; i < arr.length; i++) { 
        //Add the value to current sum 
        max_current +=arr[i]; 

        //Get the max between current sum and current value 
        max_current=Math.max(max_current, arr[i]); 

        //Update the max sum
        max_so_far=Math.max(max_so_far, max_current); 
    } 
    
    //return max 
    return max_so_far; 
};

Input:
console.log(largestSum([-8, -3, -6, -2, -5, -4, -1]));

Output:
-1

Time complexity: O(n).
Space complexity: O(1).