夕拾算法进阶篇：13)最大连续子序列(动态规划DP)

0 -2 -1

先不考虑其序列的首末位置，考虑数组A[i]={-2,11,-4,13,-5,-2}。令状态dp[i]表示以A[i]作为末尾的连续和的最大和，那么有以下过程

dp[0]=-2

dp[1]=11 (11+-4=7)

dp[3] =20 (11+(-4)+13=20)

dp[4]=15 (20-5=15)

dp[5]=13  (15-2=13)

事实上，最大和就是max(dp[i])，从而可以得到下面的状态转移方程：

dp[i]=max(A[i],dp[i-1]+A[i])    (边界为A[0]=dp[0])

很明显，dp[i]具有状态无关性。dp[i]只跟当前的A[i]和它上一个dp[i-1]无关。所有只用2个变量即可记录序列的起始位置。

#include<iostream>#include<algorithm>using namespace std; const int M=10002;int a[M];int dp[M];int main(){	//ts->temp start,te->temp end,fs->final start	int n,i,max,fs,fe,ts,te;	while(scanf("%d",&n),n){		for(i=0;i<n;i++){			scanf("%d",a+i);		}		max=te=ts=dp[0]=a[0];		for(i=1;i<n;i++){			if(dp[i-1]+a[i]>a[i]){				dp[i]=dp[i-1]+a[i];				te=a[i]; //修改末端位置 			}else{				dp[i]=te=ts=a[i];//重新开始 			}			if(max<dp[i]){//取最大的dp 				max=dp[i];fe=te;fs=ts;			}		}		if(max<0){ //所有数都小于0 		 	max=0;fs=a[0];fe=a[n-1];		}		PRintf("%d %d %d/n",max,fs,fe);	}}题目来源：http://www.codeup.cn/problem.php?cid=100000626&pid=0