# Kadane's algorithm(max sum subarray)

Kadane’s algorithm begins with simple inductive question:

" if we know that maximum subarray sum ending at position i (let it be Bi) in array,
then what is the maximum sum ending at position (i+1)(let it be Bi+1) in array.
"

The `answer` to this question is :: either it is max subarray ending at `i+1` position including the max sum ending at `i'th` position or it doesn’t

Bi+1=max( Ai+1, Ai+1 + Bi) where Ai+1 is elemnt at i+1 position.

Example:

• If max_sum+(+ve integer) =(max_sum increased)
• If max_sum+(-ve integer)=(max _sum decreased)
• In array `{5,-9}` there is no need to include `(-9)` in sum cause will make it negative hence max sum is`(5).`
• In array `{6,-2,3}` we have to include`{-2}` as max sum is`(6+(-2)+3)=7` which is grater than any integer in array.

Let’s take example:

A =`[2 -1 2 3 4 -5]` then max sum=10 with the maxsum subarray `[2 -1 2 3 4].` Below is the implementation of `Kadane’s algorithm` to find max sum contagious subarray

`````` int MaxSumArray(vector<int>& v) {
int maxsum=0;
int curr=0;
for(int i=0;i<v.size();i++){
curr=curr+v[i];
if(curr<0){curr=0;}
if(curr>maxsum){maxsum=curr;}
}
return maxsum;
}
``````

the above cpp code shows the implementaion of maxsum subarray.
now lets modify the question now we have to find max_sum of non-cotigeous subarray[subseqence]

Let’s take same example:: `[2 -1 2 3 4 -5]` now the subsequnce max_sum is=11 `[2 2 3 4]`

modified code:

``````void GetSum( vector<int>&v){
int curr=0,maxsum=0,subseq=0;
for(int i=0;i<v.size();i++){
curr=curr+v[i];
if(curr<0){curr=0;}
if(v[i]>0){subseq=subseq+v[i];}
if(curr>maxsum){maxsum=curr;}
}
cout<<"subarray_sum"<<maxsum;
cout<<"subsequnce_sum"<<subseq;
}
``````

`CORNER-CASE::` if all array elements are negative you can make max_subarray sum

1)least neagtive one(like in array -3,-5,-6 sum=-3)
2)0
3)or you can make sum=`INT_MIN.`

3 Likes