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

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

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

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

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

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