Kadane's Algorithm

#1

What is the logic behind the kadane’s algorithm?
I’m able to understand the logic behind code but not that of algorithm or approach.

#2

This is the algo of kadane’s algo
Initialize:
max_so_far = 0
max_ending_here = 0

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
(c ) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far

The idea of the Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here 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

consider the example:

{-2, -3, 4, -1, -2, 1, 5, -3}

max_so_far = max_ending_here = 0

for i=0, a[0] = -2 max_ending_here = max_ending_here + (-2) Set max_ending_here = 0 because max_ending_here < 0

for i=1, a[1] = -3 max_ending_here = max_ending_here + (-3) Set max_ending_here = 0 because max_ending_here < 0

for i=2, a[2] = 4 max_ending_here = max_ending_here + (4) max_ending_here = 4 max_so_far is updated to 4 because max_ending_here greater than max_so_far which was 0 till now

for i=3, a[3] = -1 max_ending_here = max_ending_here + (-1) max_ending_here = 3

for i=4, a[4] = -2 max_ending_here = max_ending_here + (-2) max_ending_here = 1

for i=5, a[5] = 1 max_ending_here = max_ending_here + (1) max_ending_here = 2

for i=6, a[6] = 5 max_ending_here = max_ending_here + (5) max_ending_here = 7 max_so_far is updated to 7 because max_ending_here is greater than max_so_far

for i=7, a[7] = -3 max_ending_here = max_ending_here + (-3) max_ending_here = 4

best way to understand any algorithm is to dry run on some examples

In case of any doubt feel free to ask :slight_smile:
mark your doubt as resolved if you got the answer

#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.