Advertisement here

Max Contiguous Subarray (Kadane's Algorithm)

Abhay Tiwari
25 Aug, 2021
 Given an array, [-2, 1, -3, 4, -1, 2, 1, -5, 4]
 
Task: Find a continuous subarray with maximum sum

Solution :
            Note that, we need to have a continuous subarray, which means we cannot skip an element and then go for the next element and include that in our subarray.
            So, at every step, we have this constraint that whether to include the next element and carry on with the previously
made subarray or another option is to stop the subarray and start the next subarray with the next element.
Eg. in the above array,
Let [-2] be our initial subarray,
So,
Subarray sum
[-2]           -2

        The next element is '1', now we have to make a choice whether to include '1' in the above subarray or not.
If we include '1' in the subarray, then
  • subarray: [-2,1] sum=(-1)........eq1
                However, if we don't include it in the subarray then we have to start a new subarray due to the 'continuous subarray' constraint and end the previous subarray [-2], so our new subarray will be,
  • subarray: [1] sum=(1)............eq2
        Since the sum is maximum in the case of eq2, that's why we start a new subarray.
Now considering the next element '-3', should we include it in our current subarray?
Let's see,
If we include
  • subarray:[1,-3] sum=(-2)..........eq3
            However, if we don't include then we have to stop the subarray [1] and start a new subarray because of course, we cannot skip elements (remember the constraint). And in that case, our new subarray with be:
  • subarray:[-3] sum=(-3)..............eq4
        Hence, we make the decision to include -3 in the subarray since our sum will be maximum in that case.
        This decision-making has to be done every next element.
Also to get the maximum sum, we need a variable that compares the 'sum' that we got at every final decision step and stores the maximum sum of all sums that we got.
This algorithm is called Kadane's algorithm.
Time Complexity: O(n)
Space Complexity: O(1)
Below are codes of a function that takes the array and returns the maximum sum.

Java:
1
2
3
4
5
6
7
8
9
public static int maxSubArray(int[] A) {
        int maxSoFar=A[0], maxEndingHere=A[0];
        for (int i=1;i<A.length;++i)
        {
            maxEndingHere= Math.max(maxEndingHere+A[i],A[i]);
            maxSoFar=Math.max(maxSoFar, maxEndingHere);
        }
    return maxSoFar;
}

C++:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int maxSubArray(vector < int > & a) {
  int n = a.size();
  //kadane's algo
  int maxEndingHere = a[0];
  int maxSoFar = a[0];
  for (int i = 1; i < n; i++) {
   // comparing new subarrays that will be formed for its maximum
    maxEndingHere = max(maxEndingHere + a[i], a[i]); 
    maxSoFar = max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
}

Python:
1
2
3
4
5
6
7
8
def maxSubArray(self, A):
    if not A:
        return 0
    curSum = maxSum = A[0]
    for num in A[1:]:
        curSum = max(num, curSum + num)
        maxSum = max(maxSum, curSum)
    return maxSum



Comment if there is any doubt.
Have a good day.
Next Post Previous Post
No Comment
Add Comment
comment url
Advertisement here