C语言代码:
int MaxSubsequenceSum(const int A[], int N)
{
int ThisSum, MaxSum, j;
ThisSum = MaxSum = 0;
for (j = 0; j < N; j++)
{
ThisSum += A[j];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
else if (ThisSum < 0)
ThisSum = 0;
}
return MaxSum;
}
求证:这个算法的正确性,即能够求出最后的正确的最大子序列和。
证明:
我们可以取一个通常的待求最大子序列和的数列:
(a_1,a_2,a_3...a_{p-1},a_p,a_{p+1}...a_n)
这个数列一共有n项,我们可以先排除(a_1)为负数的情况,因为这会被自动地归零处理。
然后我们设(a_p)为这个序列的第一个断点,就是(a_p)之气的所有项之和ThisSum都没有因为序列和变成负数而归零重置过,然后我们将要证的命题进行转化-->我们知道(a_1)和(a_p)这两个数是可以排除作为新的子序列的起点的,所以,我们只需要证明:
- 在(a_2)到(a_{p-1})(包括边界,下同)之间不可能存在有子序列的和比从(a1)到(a_{p-1})之间按照算法取出来的子序列和最大值要大;
- 在(a_2)和(a_{p-1})之间不会存在一个数(a_x),使(a_x)到(a_p)之间所有数之和为非负数。
下面我们就用反证法来证明这两点的正确性:
首先,我们要明确一个前提,就是从(a_1)到(a_{p-1})之间任何一个以(a_1)为起点的子序列的和都是非负数。
- 对于第一点,我们假设存在一个符合条件的子序列,其起点为(a_x, 1 < x < p - 1),其所包含的所有数之和比从(a1)到(a_{p-1})之间按照算法取出来的子序列和最大值要大。然后,根据我们的前提,我们知道索引x之前的一直到起点的子序列和一定是非负的,所以我们假设的那个子序列就还可以变得更大,如果加上所有前面的数的话,可是,这就与假设的序列和比从(a1)到(a_{p-1})之间按照算法取出来的子序列和最大值要大这一条件相矛盾了,故,假设不成立。
- 对于第二点,我们假设在(a_1)和(a_{p-1})之间存在一个数(a_x),使(a_x)到(a_p)之间所有数之和为非负数,那么根据前提,我们加上(a_x)前面的所有的数,结果还是为非负的,可是,由于(a_p)是断点,即ThisSum < 0,然而根据假设却得出相反的结论,所以假设不成立。
到这里,第一个断点之后的情况也显然得证,由此,该待证命题的正确性得证。
感谢我的同学万某,是他与我一起想出并完善了这个证明的证法。