求最大子序列和问题的四种算法

定义：给定整数A_{1}，A_{2}，A_{3},……，A_{N}(可能有复数），求\sum_{k=i}^jA_{k}的最大值（为方便起见，如果所有整数均为负数，则最大子序列和为0）。

算法一:

int MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum, MaxSum, i, j, k;
    MaxSum = 0;
    for(i=0; i<N; i++)
        for(j=i; j<N; j++)
        {
            ThisSum = 0;
            for(k=i; k<=j; k++)
            {
                ThisSum += A[k];
            }
            if(ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    return MaxSum;
}

注：该种算法会进行大量不必要的计算，运行效率较低。

算法二:

int MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum, MaxSum, i, j;
    MaxSum = 0;
    for(i = 0; i < N; i++)
    {
        ThisSum = 0;
        for(j = i; j < N; j++)
        {
            ThisSum += A[j];
            if(ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    }
    return MaxSum;
}

注：算法二是算法一的改进版本，相比于算法一，算法二减少了一个for循环，减少了不必要运算，提高了运行效率。

算法三：

    static int MaxSubSum(const int A[], int Left, int Right)
    {
        int MaxLeftSum, MaxRightSum;
        int MaxLeftBorderSum, MaxRightBorderSum;
        int LeftBorderSum, RightBorderSum;
        int Center, i;
        if(Left == Right)   /*Base Case*/
            if(A[Left] > 0)
                return A[Left];
            else
                return 0;
        Center = (Left + Right)/2;

        MaxLeftSum = MaxSubSum(A, Left, Center);
        MaxRightSum = MaxSubSum(A ,Center + 1, Right);

        MaxLeftBorderSum = 0;
        LeftBorderSum = 0;
        for(i = Center; i >= Left; i--)
        {
            LeftBorderSum += A[i];
            if(LeftBorderSum > MaxLeftBorderSum)
                MaxLeftBorderSum = LeftBorderSum;
        }

        MaxRightBorderSum = 0;
        RightBorderSum = 0;
        for(i = Center + 1; i <= Right; i++)
        {
            RightBorderSum += A[i];
            if(RightBorderSum > MaxRightBorderSum)
                MaxRightBorderSum = RightBorderSum;
        }
        return MAX3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum); /*伪代码，取三个数值中最大的一个*/
    }


    int MaxSubsequenceSum(const int A[], int N)
    {
        return MaxSubSum(A,0,N-1);
    }

注：算法三采用了“分治”策略，它的代码虽然长，但比算法二更加高效。其想法是把问题分成两个大致相等的子问题，然后递归地对它们求解，这是“分”部分。“治”阶段将两个子问题的解合并到一起并可能再做些少量的附加工作，最后得到整个问题的解。
在求最大子序列和的问题中，最大子序列和可能在三处出现。或者出现在输入数据的左半部，或者出现在输入数据的右半部，或者跨越输入数据的中部从而占据左右两半部分。
前两种情况可以用递归求解。第三种情况的最大和可以通过求出前半部分的最大和（包含前半部分的最后一个元素）以及后半部分的最大和（包含后半部分的第一个元素）而得到。然后将这两个和加在一起。

算法四：

    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;
    }

注：算法四只用了一个for循环，实现起来比递归算法简单而且更为有效。