Largest sum contiguous subarray (Kadane’s algorithm)

Largest sum contiguous subarray

Given an array of signed integers, find largest sum contiguous subarray. It mean find subarray with maximum sum from given array. Subarray is continuous indices of array with size ranging from 0 to N where N is size of original array. For example, for array [ -1, 3, -5, 4, 6, -1, 2, -7, 13, -3 ], output is subarray [ 4,6,-1,2,-7,13 ] with sum = 17. Largest sum contiguous subarray problem is solved using Kadane’s algorithm

Maximum sum subarray can be found using dynamic programming approach. At each element in input array, take decision whether to include current element into longest subarray till now or not to include current element. This is made based on following considerations:

1. If element at index i increases sum of subarray ending at index i-1, then it should be included in subarray.
2. If element at index i, when added to sum of subarray ending at i-1 makes sum negative, number is not included. Because adding it will make all subsequent sums less than what already is available with subarray ending at i-1. To summarize,

To calculate sum till index i, we can use sum we have already calculated till i-1 index.
If adding element at i makes the sum negative, we would drop the element, as having this element in the sub array will only decrease the already existing sum as well as sum all the elements subsequent of this element. Hence we would start afresh from i+1 element.

Second thing is that even if sum is greater than zero after taking ith element, check if it greater than sum till i-1 index.

Largest sum contiguous subarray : Inclusion algorithm

  • If addition of ith element makes sum of subarray negative, make current sum as zero and start all over again with i+1 index.
  • If sum is greater than sum of subarray ending i-1 index, then ith element is added in the sub array and rightmost index of sub array becomes i.
  • If  sum is less than max sum till i-1 index, then don’t change rightmost index of sub array.

Above algorithm to maximum sub contiguous subarray does not work with all numbers in array being negative. To handle that case, scan all elements of array prior to application of algorithm and see if there is at least one non-negative number in array. Also, during this phase keep track of the largest number seen. If all elements are negative, return largest number.

Largest sum contiguous subarray implementation


#include <stdio.h>
 
void largestSumContiguousSubarray(int a[], int size){
 
    int startIndex = 0, endIndex = 0;
    int index;
    int currStartIndex = 0;
 
    int maxSum = 0;
    int currentSum = 0;
 
    for(index = 0 ; index < size; index++){
        currentSum  = currentSum + a[index];
        // case 1 : When ith element can be included
        // Change the end index and also update the start index.
        if(currentSum > maxSum){
            maxSum = currentSum;
            endIndex = index;
            startIndex = currStartIndex;
        }
        /*case 2 : When ith index cannot be included and 
        we need to start with i+1 index. till now our max sum
        and start and end index of that sum remain same */
        if(currentSum < 0){
            currStartIndex = index + 1;
            currentSum = 0;
        }
    }
    printf("\nMaximum Sum : %d", maxSum);
    printf("\nBetween (%d, %d)", startIndex, endIndex);
}
 
//Driver program
int main() {
 
   int intArr[] = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
   int size = sizeof(intArr)/sizeof(intArr[0]);
   largestSumContiguousSubarray(intArr, size);
 
    return 0;
}

Let’s trace the execution of code and see if algorithm is working properly or not?
main() function calls lcsum (a, size) with a = [-1, 3, -5, 4, 6, -1, 2, -7, 13, -3 ] and size =  10.
We will scan from i=0 to i =10 using a for loop at line 10 and keep track o four counters. maxSum stores maximum sum of subarray till index i. currentSum store the sum of currently running subarray sum. These two may differ. startIndex which keeps track of start index of subarray with maxSum and endIndex which keeps track of last index. currStartIndex and currEndIndex indicate start and end index respectively of current subarray being considered. To start with startIndex = endIndex = currStartIndex = currEndIndex = 0. Also, currSum and maxSum are 0.

For i =0; currSum  = 0 + -1 = -1.  Condition that sum should be greater than 0 for index to considered as part of solution, index 0 is discarded from solution. First condition (maxSum < currSum) is false, so none of statements in that if block is executed. Second condition (currSum < 0) is true, hence we will move currStartIndex = i + 1  = 1 and reset currSum = 0.
After first run maxSum = 0, currSum = 0, startIndex = currStartIndex = 1. endIndex still need to be found.

Now, for i = 1; currSum = 0 + 3 =3. First condition (maxSum < currSum) is true, hence maxSum is updated to 3, endIndex = 1 and startIndex = 1. So our probable subarray with maxSum is [3] with maxSum =3. Second condition is false.

For i = 2; currSum =  3 + (-5) = -2. First condition (maxSum < currSum) is false, so none of statements in that if block are executed. Second condition (currSum < 0) is true, hence we will move currStartIndex = i + 1  = 3 and reset currSum = 0.
Now, maxSum = 3, currSum = 0, startIndex = currStartIndex = endIndex = 1.

For i =3; currSum  = 0 + 4 =4
First condition (maxSum < currSum) (maxSum so far is 3) is true, hence maxSum is updated to 4, startIndex = 3 and endIndex = 3. So our probable subarray with maxSum is [4] with maxSum = 4.
Second condition is false.

For i =4; currSum = 4 + 6 = 10
First condition (maxSum < currSum) (maxSum so far is 4) is true, hence maxSum is updated to 10, startIndex = 3 and endIndex = 4. So our probable subarray with maxSum is [4,6] with maxSum =10. Second condition is false.

For i =5; currSum = 10 + (-1) = 9
First condition (maxSum < currSum) (maxSum = 10) is false, so none of statements in that if block is executed. Second condition (currSum < 0) is also false, nothing is executed.
Now, maxSum = 10, currSum = 9, startIndex = 3 endIndex = 4.

For i =6; currSum = 9 + 2 = 11.
First condition (maxSum < currSum) (maxSum so far is 10) is true, hence maxSum is updated to 11, startIndex = 3 and endIndex = 6. So our probable subarray with maxSum is [4,6,-1,2 ] with maxSum =11.
Second condition is false.

For i =7; currSum = 11 + (-7) = 4.
First condition (maxSum < currSum) is false, hence nothing executed in that block, also, currentSum is not less than 0, hence, startIndex = 3 and endIndex = 6. So  still probable subarray with maxSum is [4,6,-1,2 ] with maxSum =11.

For i =8; currSum = 4+ 13 = 17.
First condition (maxSum < currSum) (maxSum so far is 11) is true, hence maxSum is updated to 17, startIndex = 3 and endIndex = 8. Probable subarray with maxSum is [4,6,-1,2,-7,13 ] with maxSum =17.
Second condition is false.

For i =9; currSum = 17 + (-3) = 14.
First condition (maxSum < currSum) is false, hence nothing executed in that block, also, currentSum is not less than 0, hence, startIndex = 3 and endIndex = 8. So  still probable subarray with maxSum is [4,6,-1,2,-7,13 ] with maxSum =17.

Complexity of algorithm to find largest sum contiguous subarray using Kadane’s algorithm is O(N) in time and O(1) in space.

Please share if there is something missing or wrong. If you are interested in contributing to website, please contact us.

  • M8

    > Complexity of above code is O(N) in time and O(N) in space.

    It should be linear time and constant space.

    • http://algorithmsandme.in/ Jitendra Sangar

      Agree. corrected.

  • ishan

    hi
    i tried ur code for the array below and it summed correct, but starting and end positions are not correct.
    {9,2,10,-1,-2,5,-3,3,-4,-1}

    plz recheck it..

    • http://algorithmsandme.in/ Jitendra Sangar

      Let me check and revert

  • juan lu

    I don’t actually understand how the code works.can you please tell me why we reset the the curSum =0 when we find after adding a[index],the surSum becomes less than zero?

    • http://algorithmsandme.com/ Jitendra Sangar

      It becomes zero because, there cannot be a subarray in largest sum subarray which adds up negative.
      You know what I mean, if we add that part into final subarray, the sum of it will be less than what it will be if don’t include the other subarray with negative sum. That’s why we start fresh with curSum as zero.

      Hope this helps!!

  • Moin Anjanawala

    { 4, 6, -1, 2, -7, 13 } = 17
    This is supposed to be maximum contigious subarray