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