題目1011：最大連續子序列 時間限制：1 秒內存限制：32 兆特殊判題：否提交：2456解決：1190 題目描述： 給定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 [cpp] #include <stdio.h> int main() { int k,i,a[10000],sum,tempsum,begin,end,position,count,zero; bool negative,first; while(scanf("%d",&k),k) { sum=tempsum=begin=end=position=count=0; negative=true; first=true; for(i=0; i<k; i++) scanf("%d",&a[i]); for(i=0; i<k; i++) { tempsum+=a[i]; //記下第一次0出現的位置 if(a[i]==0 && first) {zero=i;first=false;}; if(a[i]>=0) negative=false; if(tempsum<0) { tempsum=0; position=i+1;//當前位置和為負 從下個位置開始 } //不能等於 否則沒法保證是下標小的序列 if(tempsum>sum) { sum=tempsum; begin=position; end=i; } } if(sum==0) { if(negative)//全負 printf("%d %d %d\n",0,a[0],a[k-1]); else printf("%d %d %d\n",0,a[zero],a[zero]); } else printf("%d %d %d\n",sum,a[begin],a[end]); } return 0; } /************************************************************** Problem: 1011 User: windzhu Language: C++ Result: Accepted Time:20 ms Memory:1012 kb ****************************************************************/
