最大子列和

发表于 阅读次数： 本文字数： 972 阅读时长 ≈ 1 分钟

最大子列和问题，即给定N个整数的序列\(\{A_1,A_2,\ldots,A_N \}\)，求函数\(f(i,j)=max\lbrace 0,\sum\limits_{i=0}^n{A_k}\rbrace\)的最大值。 例如\(\lbrace-2,11,-4,13,-5,-2\rbrace\)的最大子列和为20，子列为\(\lbrace11,-4,13\rbrace\). \(\lbrace-10, 1, 2, 3, 4, -5, -23, 3, 7, -21\rbrace\)的最大子列和为10，子列为\(\lbrace1，2，3，4\rbrace\)。 本文将给出实现这种算法的\(\Theta(N^2)\)和\(\Theta(N)\)算法

\(\Theta(N^2)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int MaxSubseqSum(int A[], int N)
{
    int ThisSum,MaxSum=0;
    int i,j;
    for(i=0;i<N;i++)    //i是子列左端位置
    {
        ThisSum=0;      //ThisSum是从A[i]到A[j]的子列和
        for(j = i; j < N; j++)//j是子列右端位置
        {
            ThisSum += A[j];  //对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可
            if(ThisSum > MaxSum) //如果刚得到的这个子列和更大
                MaxSum = ThisSum; //则更新结果
        }
    }
    return MaxSum;
}

\(\Theta(N)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int MaxSubseqSum(int A[], int N)
{
    int ThisSum, MaxSum;
    int i;
    ThisSum = MaxSum = 0;
    for(i = 0; i < N; i++)
    {
        ThisSum += A[i];        //向右累加
        if(ThisSum > MaxSum)
            MaxSum = ThisSum;   //发现更大和则更新当前结果
        else if(ThisSum < 0)    //如果当前子列和为负
            ThisSum = 0;        //则不可能使后面的部分和增大，抛弃之
    }
    return MaxSum;
}

第二种方法可能不是很好理解，有必要的话可以根据上面的例子手动推演一下。