求给定序列的最大连续序列的和

  • 问题描述
    给定n个数(可以为负数)的序列(a1,a2,…,an)，求$max(0,\sum_{k=i}^{j} a_k)\space 1≤i≤j≤n$
  • 子问题界定
    设前边界为1,后边界为i,且$C[i]$是以$A[i]$为结尾的连续子段的和的最大值.
  • 递推方程
    $$C[i]=max(C[i-1]+A[i],A[i]) \space i=2,…,n$$
    $$C[1]=max(A[1],0)$$
  • 时间复杂度:$O(n)$
  • 代码实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    #include<iostream>
    using namespace std;

    int MaxSubsequenceSum(const int A[], int n)
    {
        int tempSum = 0;
        int maxSum = 0;
        for (int j = 0;j < n;j++)   // 子问题后边界
        {
            tempSum = (tempSum + A[j]) > A[j] ? (tempSum + A[j]) : A[j];
            if (tempSum > maxSum)   // 更新最大和
                maxSum = tempSum;

        }
        return maxSum;
    }

    int main()
    {
        const int a[] = { 4, -3, 5, -2, -1, 2, 6, -2 };
        int maxSubSum = MaxSubsequenceSum(a, 8);
        cout << "The max subsequence sum of a is: " << maxSubSum << endl;
        system("pause");
        return 0;
    }