1231.txt

来自「浙江大学研究生复试上机题目及解答。欢迎大家下载。」· 文本 代码 · 共 39 行

#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;
}