algorithm - 证明暴力最大子数组算法的正确性

Question

我试图证明下面给出的最大子数组问题的蛮力版本的正确性：

def max_subarray_bf(lst):
    left = 0
    right = 0
    max = lst[0]
    for i in range(len(lst)):
        current_sum=0
        for j in range(i, len(lst)):
            current_sum+=lst[j]
            if current_sum>max:
                max=current_sum
                left=i
                right=j
    return (left, right, max)

但我似乎被困在设计循环不变量上，这可能是因为内部循环改变了一个全局变量（max），这使得我很难描述（max）在对应于内部循环的循环不变量中代表什么。

我的尝试：

总体而言，该算法通过查找以下子数组的最大子数组来工作：

{[0],[0,1],...,[0,...,n]

 [1],[1,2],...,[1,...,n]

 .

 .

 .

 [n]}

• 内循环不变量：
  • Current_sum 是数组 [i...j] 中所有元素的总和
  • 卡在这里，因为我似乎无法捕捉到 i 和 j 的最大值，因此左和右