九度OJ—題目1011：最大連續子序列

上一篇/kf/201412/363594.html

題目描述： 給定K個整數的序列{ N1, N2, ..., NK }，其任意連續子序列可表示為{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。最大連續子序列是所有連續子序列中元素和最大的一個，例如給定序列{ -2, 11, -4, 13, -5, -2 }，其最大連續子序列為{ 11, -4, 13 }，最大和為20。現在增加一個要求，即還需要輸出該子序列的第一個和最後一個元素。 輸入：

測試輸入包含若干測試用例，每個測試用例占2行，第1行給出正整數K( K< 10000 )，第2行給出K個整數，中間用空格分隔。當K為0時，輸入結束，該用例不被處理。

輸出：

對每個測試用例，在1行裡輸出最大和、最大連續子序列的第一個和最後一個元素，中間用空格分隔。如果最大連續子序列不唯一，則輸出序號i和j最小的那個（如輸入樣例的第2、3組）。若所有K個元素都是負數，則定義其最大和為0，輸出整個序列的首尾元素。

樣例輸入：

6
-2 11 -4 13 -5 -2
10
-10 1 2 3 4 -5 -23 3 7 -21
6
5 -8 3 2 5 0
1
10
3
-1 -5 -2
3
-1 0 -2
0

樣例輸出：

20 11 13
10 1 4
10 3 5
10 10 10
0 -1 -2
0 0 0

來源：

2005年浙江大學計算機及軟件工程研究生機試真題 答疑：

解題遇到問題?分享解題心得?討論本題請訪問：www.2cto.com

 

 

#include
using namespace std;
 
int main()
{
    int n,i,s[10000],a[10000],f[10000],max,st,end;  //f[i]為以i為結尾最長連續序列，s[i]為其開始點
    bool flag;
    while(cin>>n && n!=0)
    {
        for(i=0;i>a[i];
        flag=0;
        for(i=0;i=0)
            {flag=1;break;}
        if(flag)   //不是全負
        {
              f[0]=a[0];
              s[0]=0;
              for(i=1;i=a[i])
                {
                    f[i]=f[i-1]+a[i];
                    s[i]=s[i-1];
                }
                else
                {
                    f[i]=a[i];
                    s[i]=i;
                }
              }
             max=f[0];
             st=0;
             end=0;
             for(i=1;imax)
                {
                    max=f[i];
                    st=s[i];
                    end=i;
                }
             }
            cout<