hdu 1231 최대 연속 서브 시퀀스 동적 계획

동적 전이 방정식 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<iostream>
#include<stdio.h>
#include<memory.h>
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<<dp[i]<<" "<<a[start[i]]<<" "<<a[i]<<endl;
					break;
				}
			}
		}
		else{
			printf("0 %d %d
",a[1],a[n]);
		}
	}
}