# Code Avinya

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.

• 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.

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).