Kadane's algorithm(max sum subarray)

general
1

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.:crazy_face:

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.:upside_down_face:

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] :sunglasses:

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