美文网首页
2018-07-25

2018-07-25

作者: 清风碧水 | 来源:发表于2018-07-25 08:57 被阅读0次

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

定义:给定整数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循环,实现起来比递归算法简单而且更为有效。

相关文章

网友评论

      本文标题:2018-07-25

      本文链接:https://www.haomeiwen.com/subject/zjvumftx.html