动态规划问题：最大连续子序列和

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

样例：

-2 11 -4 13 -5 -2
显然11+（-4）+13=20为和最大的选取情况，因此最大和为20。

使用暴力法来解决这个问题，枚举左端点和右端点（即枚举i，j）需要O(n ^2)的复杂度，而计算A[i]+…+A[j]需要O(n)的复杂度，所以总复杂度为O(n ^3)。
动态规划的做法：复杂度为O(n)。

步骤1：令状态dp[i]表示以A[i]作为末尾的连续序列的最大和。

dp[0]=-2,
dp[1]=11,
dp[2]=7(11+(-4)=7),
dp[3]=20(11+(-4)+13=20),
dp[4]=15(因为由dp数组的含义，A[4]=-5必须作为连续序列的结尾，于是最大和就是11+(-4)+14+(-5)=15,而不是20)，
dp[5]=13(11+(-4)+14+(-5)+(-2)=13)

步骤2：因为dp[i]要求是必须以A[i]结尾的连续序列，那么只有两种情况：

1. 这个最大和的连续序列只有一个元素，即以A[i]开始，以A[i]结尾
2. 这个最大和的连续序列有多个元素，即从前面某处A[p]开始（p<i）,一直到A[i]结尾。
   对于第一种情况，最大和就是A[i]本身。
   对于第二种情况，最大和就是dp[i-1]+A[i],即A[p]+…+A[i-1]+A[i]=dp[i-1] + A[i]。
   综上得到状态转移方程：dp[i]=max{A[i],dp[i-1]+A[i]}

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1010;
int A[maxn],dp[maxn];
int main()
{
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
                scanf("%d",&A[i]);
        }
        //bianjie
        dp[0]=A[0];
        for(int i=1;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;
                }
        }
        printf("%d\n",dp[k]);
        return 0;
}

整理自《算法笔记》