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.