Kadane’s Algorithm
The famous max sum of contiguous subarray problem can be solved using Kadanes Algorithm.
Suppose you need to find the largest sum contiguous subarray. You could say I can do it in O(n^2) using two for loops. What if I say we can do it in O(n)? There is where Kadene’s Algorithm comes into the picture.
Before jumping into the code let’s try to understand the intuition behind Kadane’s algorithm.
Kadane’s Algorithm Intuition
- A[0]……A[i]….A[j]……A[n-1]
- assume the sum_here variable indicates the sum of the elements of a sub-array(A[I] to A[j]).
- Now let’s say we want to include A[j+1] in our sub-array.
Now our new sum_here = max(sum_here+A[j+1], A[j+1]);
It is a maximum of those two. Because this is what the question requirement is right.
Now let’s see Kadens Algo:
int mx_sum=INT_MIN; // Initialsing with negative infinity. As array can also contain non negative numbers.
int sum_here=0;
for(int i=0;i<n;i++)
{
sum_here = max(sum_here+a[i], a[i]);// It will store subarray sum till here i.e till i
mx_sum = max(mx_sum, sum_here); // our max sum will get updated
}
cout<<"Maximum subaaray sum is"<<mx_sum<<endl;
Complexity Analysis of Kadane’s Algorithm
Time complexity is O(n) and space complexity is O(1).