動態轉移方程dp[i]=max(dp[i-1]+a[i],a[i]);
dp[i]表示一這個點結尾的最大連續子序列
因為還要記錄序列的頭和尾,用start[]記錄每個點在該序列的起始位置
注意提示要用scanf啊,cin會TLE
/************************************************************************* > File Name: hdu1231.cpp > Author: yang > Mail:[email protected] > Created Time: 2014年08月24日 星期日 20:01:52 ************************************************************************/ #include#include #include using namespace std; #define N 10005 int main(){ int n; int a[N],dp[N],start[N]; while(scanf("%d",&n),n){ int flag=0,cou=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); dp[i]=0; if(a[i]<0) cou++; } if(cou==n) flag=1; int x=1; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ if(dp[i-1]+a[i]>=a[i]) dp[i]=dp[i-1]+a[i]; else{ x=i; dp[i]=a[i]; } start[i]=x; } if(flag==0){ cou=0; for(int i=1;i<=n;i++) if(dp[i]>cou) cou=dp[i]; for(int i=1;i<=n;i++){ if(cou==dp[i]){ cout<