**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.`