algorithm - 对 Kadane 的算法感到困惑？

Question

我查找了寻找连续子数组最大和的最优解。还有一种算法叫做 Kadane 算法。这是我在 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

我不明白的部分是(b)，为什么这里的max_ending小于0时这里的max_ending设置为0？这背后的直觉是什么？

Answer 1

您想重置最大值，因为任何可能抵消最大值的潜在负数组元素。

例如，

2 3 -6 4 2

在元素 -6 处，如果您不在此处重置最大值，那么您会将 -1 的最大值带入下一次迭代。