Kadanes algorithm doubt

#1

why we are replacing -ve value of ‘cs’ with 0 ???
I do not get the logic of kadanes algo.
Bhaiya please explain the logic in detail.

#2

And what if all the values in array are negative…then the maximum sum will be 0 ???

#3

Kadane’s Algorithm:

Initialize:
    max_so_far = INT_MIN
    cumSum = 0

Loop for each element of the array
  (a) cumSum = cumSum+ a[i]
  (b) if(max_so_far < cumSum)
            max_so_far = cumSum
  (c) if(cumSum< 0)
            cumSum= 0
return max_so_far

Explanation:
The simple idea of Kadane’s algorithm is to look for all positive contiguous segments of the array (cumSum is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive-sum compare it with max_so_far and update max_so_far if it is greater than max_so_far

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.