confusion about Kadane’s Algorithm?

Question

I looked up the optimal solution for finding largest sum of continuous subarray. And there's algorithm called Kadane's algorithm. Here is pseduocode I found on geeksforgeeks.

 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 part I don't understand is (b), why is max_ending here set to 0 when max_ending here is less than 0?? what's the intuition behind this?

Answer 1

You want to reset the max because of any potential negative array elements that may offset the max.

for example,

2 3 -6 4 2

at element -6, if you don't reset the max here then you carry the max of -1 into the next iteration.

Answer 2

If max_ending_here is less than 0 going into part (b), that means that the maximum sum making use of this element is less than 0. There's a better sum than that ending here, which is to just take a length-0 subarray. That's what we do in part (b).

Basically, if we enter the if in part (b), we're throwing away all previous elements and starting the subarray from scratch.