0 -2 -1

先不考慮其序列的首末位置，考慮數(shù)組A[i]={-2,11,-4,13,-5,-2}。令狀態(tài)dp[i]表示以A[i]作為末尾的連續(xù)和的最大和，那么有以下過程

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)

事實(shí)上，最大和就是max(dp[i])，從而可以得到下面的狀態(tài)轉(zhuǎn)移方程：

dp[i]=max(A[i],dp[i-1]+A[i])    (邊界為A[0]=dp[0])

很明顯，dp[i]具有狀態(tài)無關(guān)性。dp[i]只跟當(dāng)前的A[i]和它上一個(gè)dp[i-1]無關(guān)。所有只用2個(gè)變量即可記錄序列的起始位置。

#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){ //所有數(shù)都小于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