What is the logic behind cumulative sum in the video Max. subarray sum2? Please explain the code as well.
Didnt understand the logic behind the maximum array sum-2
For Kadane Algorithm:
Logic is Greedy Approach:
If your array has some Positive sum P1 then some negative sum N1 then Positive sum P2
such that P1+N1>0 then P1+N1+P2 will be greater than P1 or P2.
So we are just checking whether we can create P1+N1 such that P1+N1>0 so that we can add it to P2 otherwise Maximum Value is P2 or P1.
Example 1:
array
2 5 -3 -1 4 -20 10
Here P1=7 (2+5) N1=-4 (-3 and -1) P2=4 N2=(-20) P3=10
p1+n1>0
So upto element 4 max sum is= 7 (2+5-3-1+4)
So, above question reduce to
7 -20 10
now P1= 7 N1=-20 P2=10
So, P1+N1 is not greater than 0 so answer is either 7 or 10 , so my answer is 10 which is maximum subarray sum .
Using Kadane algorithm we can write its code using one loop.
Hit like if u get it.