最大子列和

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

最大子列和问题，即给定N个整数的序列{A1,A2,…,AN}\{A_1,A_2,\ldots,A_N \}，求函数f(i,j)=max{0,∑i=0nAk}f(i,j)=max\lbrace 0,\sum\limits_{i=0}^n{A_k}\rbrace的最大值。
例如{−2,11,−4,13,−5,−2}\lbrace-2,11,-4,13,-5,-2\rbrace的最大子列和为20，子列为{11,−4,13}\lbrace11,-4,13\rbrace.
{−10,1,2,3,4,−5,−23,3,7,−21}\lbrace-10, 1, 2, 3, 4, -5, -23, 3, 7, -21\rbrace的最大子列和为10，子列为{1，2，3，4}\lbrace1，2，3，4\rbrace。

本文将给出实现这种算法的Θ(N2)\Theta(N^2)和Θ(N)\Theta(N)算法

Θ(N2)\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;
}

Θ(N)\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;
}

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