1231 最大连续子序列.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

/*
1231 最大连续子序列
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 256 K

GUN C++
*/
#include <iostream>
#include <cstdio>
using namespace std;

const int kMax=10000;
int in[kMax];
int dp[kMax],index[kMax];

int main()
{
    int k,i,max,ii,jj;

    while(scanf("%d",&k)==1 && k!=0)
    {
        for(i=0;i<k;i++)
			scanf("%d",&in[i]);
        dp[0]=in[0];
        max=in[0]>0 ? in[0] : -1;
        index[0]=0;
        ii=jj=0;
        for(i=1;i<k;i++)
        {
            if(dp[i-1]<0)
            {   dp[i]=in[i];index[i]=i;}
            else
            {   dp[i]=dp[i-1]+in[i];index[i]=i-1;}
            if(dp[i]>max)
            {   max=dp[i];jj=i;}
        }
        ii=jj;
        while(index[ii]!=ii)
            ii=index[ii];

        if(max<0)
        {   max=0;ii=0;jj=k-1;}
        cout<<max<<' '<<in[ii]<<' '<<in[jj]<<endl;
    }
    return 0;
}