Kadane's Algorithm for 1D Max Sum Subset in O(N)

Kadane's algorithm is used to find maximum sum subset in O(N) complexity.

1. Begin iteration
2. At each element the max sum subset can either be that element's value alone or max sum subset value at previous element + this elements value.
3. Record a global max while iterating.
4. Global max at end is the answer.

Consider an example array :

-1 5 6 -2 12

              cmax                          gmax
i = 0         -1                            -1
i = 1         max(-1+5, 5) = 5,             max(-1, 5) = 5
i = 2         max(5+6, 6) = 11,             max(5, 11) = 11
i = 3         max(11+(-2), -2) = 9,         max(11, 9) = 11
i = 4         max(9+12, 12) = 21,           max(11, 21) = 21

gmax = 21 is the answer

Quick Tutorial:

https://www.youtube.com/watch?v=86CQq3pKSUw

SPOJ.com Problem MAXSUMSU Link