联机算法(又叫在线处理,online algorithm)求最大子序列和的证明

2021-03-27 21:26

阅读:628

标签:没有   需要   mat   seq   数列   情况   strong   int   c语言   

C语言代码:

int MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum, MaxSum, j;
    
    ThisSum = MaxSum = 0;
    for (j = 0; j  MaxSum)
            MaxSum = ThisSum;
        else if (ThisSum 

求证:这个算法的正确性,即能够求出最后的正确的最大子序列和。

证明:

我们可以取一个通常的待求最大子序列和的数列:

\(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\)为起点的子序列的和都是非负数。

  1. 对于第一点,我们假设存在一个符合条件的子序列,其起点为\(a_x, 1 ,其所包含的所有数之和比从\(a1\)\(a_{p-1}\)之间按照算法取出来的子序列和最大值要大。然后,根据我们的前提,我们知道索引x之前的一直到起点的子序列和一定是非负的,所以我们假设的那个子序列就还可以变得更大,如果加上所有前面的数的话,可是,这就与假设的序列和比从\(a1\)\(a_{p-1}\)之间按照算法取出来的子序列和最大值要大这一条件相矛盾了,故,假设不成立。
  2. 对于第二点,我们假设在\(a_1\)\(a_{p-1}\)之间存在一个数\(a_x\),使\(a_x\)\(a_p\)之间所有数之和为非负数,那么根据前提,我们加上\(a_x\)前面的所有的数,结果还是为非负的,可是,由于\(a_p\)是断点,即ThisSum

到这里,第一个断点之后的情况也显然得证,由此,该待证命题的正确性得证。

感谢我的同学万某,是他与我一起想出并完善了这个证明的证法。

联机算法(又叫在线处理,online algorithm)求最大子序列和的证明

标签:没有   需要   mat   seq   数列   情况   strong   int   c语言   

原文地址:https://www.cnblogs.com/fanlumaster/p/13654938.html


评论


亲,登录后才可以留言!