首页 > 代码库 > HDU 1231
HDU 1231
求最大连续子序列
一开始想到的一种O(n^2)的算法,应该会超时
运用动态规划的思想,想出了下面的方法
#include <iostream>
using namespace std;
struct DP{
int sum,sta,end;
void init(int su,int st,int en){
sum=su;
sta=st;
end=en;
}
};
int a[10000];
int main()
{
int t;
while(cin>>t){
if(0==t)break;
for(int i=0;i<t;i++){
cin>>a[i];
}
DP tem,max;
tem.init(0,0,0);
max.init(a[0],0,0);
for(int i=0;i<t;i++){
tem.end=i;
tem.sum+=a[i];
if(tem.sum>max.sum&&tem.sum>=0){
max.init(tem.sum,tem.sta,tem.end);
}
if(tem.sum<0){
tem.init(0,i+1,i+1);
}
}
if(max.sum<0)cout<<"0 "<<a[0]<<" "<<a[t-1]<<endl;
else cout<<max.sum<<" "<<a[max.sta]<<" "<<a[max.end]<<endl;
}
}