最大连续子序列的和

给定一个数字序列A1，A2，…，An，求i,j(1<=i<=j<=n)，使得Ai+…+Aj最大，输出这个最大的和。

分析：这个问题如若暴力来做，枚举i,j需要O(n^2)的复杂度，而计算A[i]+…+A[j]需要O(n)的复杂度，因此总的复杂度为O(n^3)。就算采用记录前缀和的方法(预处理S[i]=A[0]+A[1]+…+A[i],这样A[i]+…+A[j]=S[j]-S[i-1])使计算的时间变为O(1)，总的复杂度仍然有O(n^2)。

这里介绍动态规划的做法，复杂度为O(n)。令状态dp[i]表示以A[i]作为末尾的连续序列的最大和(这里的连续指的是从第一个元素开始)。其实所要求的最大和就是dp数组中的最大值。也就是说求dp[i]时，只要dp[i-1]小于零就舍弃前面的和，直接取A[i]的值作为dp[i]即可；而如果dp[i-1]大于零，dp[i]就等于dp[i-1]+A[i]。于是得到dp[i]=max(A[i],dp[i-1]+A[i])。而边界就是dp[0]=A[0]。

#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;

const int maxn = 10010;
int A[maxn], dp[maxn];

int main() {
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        cin >> A[i];
    }
    dp[0] = A[0];//边界
    for (int i = 0;i < n;i++) {
        dp[i] = max(A[i], dp[i - 1] + A[i]);//状态转移方程
    }

    int k = 0;
    for (int i = 1;i < n;i++) {
        if (dp[i] > dp[k])
            k = i;
    }
    cout << dp[k];
    system("pause");
    return 0;
}