algorithm - 算法不变量

Question

假设这个算法给出了一个子数组的最大和。并设 a[] 为长度为 n 的数组。

randmax = 0
maximum = 0
for 0 <= i < n 
    randmax = randmax + a_i
    if randmax > max 
    max = randmax
    if randmax < 0 
    randmax = 0

我怎样才能找到一个循环不变量，它在执行之前，当然在循环迭代之前和之后都成立，当 n-1 时，不变量应该暗示正确的解决方案。

Answer 1

如果我理解你的问题，那么这就是 id 所说的：

初始化：总和是 0 开始，所以你的最大值是 0

维护：到目前为止的最大值是 a[0] +...+a[i-1] 的总和

终止：最大值是数组 a[0] + ... + a[n-1] 的总和。

因此，循环不变式是您在任何给定时间的总和/最大值是 a[0] + ... + a[i-1]，并且仅由在您的数组中找到的数字组成。