Flaw in Kadane's Method

#1

What if I input only negative numbers in the Kadane’s method program? e.g. -1,-2,-3,-4,-5
maximum sum should be -1 but I’d recieve 0 irrespectively.

#2

Kadane’s Algorithm:
1.Initialize:
max_so_far = 0
max_ending_here = 0

2.Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
©if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far

if you notice step (b),
it is checking for the negative sum, and resetting the value of max_ending_here to 0.

Yes, you have pointed out it correct. This is a limitation of this method. ( possibly )

Mark the doubt as resolved and if possible give a like and review about me.:wink:

#3

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.