algorithm - 算法的不变性

假设该算法给出了子阵的最大和。设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时，那么不变量应该意味着正确的解决方案。

最佳答案

如果我理解你的疑问，那么这就是我所说的：
初始化：总和为0，因此最大值为0
维护：目前的最大值是a[0]+…+a[i-1]的和
终止：最大值是数组a[0]+…+A[N-1]。
所以循环不变量是任意给定时间的和/最大值是[0]+…+a[i-1]，仅由数组中的数字组成。

关于algorithm - 算法的不变性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53054902/