PRoblem Link：http://139.129.36.234/problem.php?id=1196

題目描述

給定 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( <100000) ，第 2 行給出 K 個整數，每個整數的范圍-10000至10000 ，中間用空格分隔。當K 為0 時，輸入結束，該用例不被處理。

輸出

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

樣例輸入

86 -2 11 -4 13 -5 -2 1020-10 1 2 3 4 -5 -23 3 7 -21 6 5 -8 3 2 5 0 1 10 38-1 -5 -2 3 -1 0 -2 04 -1 -2 -4 -30
樣例輸出
27 0 727 10 193 3 30 0 0
提示
中南大學計算機&軟件復試QQ群552889929
來源
2014年中南大學研究生復試機試題
AC code：
#include<iostream>#include<algorithm>#include<stdio.h>#include<map>#include<math.h>#include<string.h>#include<queue>#include<vector>#include<set>#define LL long long#define exp 1e-9#define MAXN 1000010using namespace std;int a[100010];void MaxSubsequenceSum(int a[],int n){	int CurSum,MaxSum,i,st,ed,tmp;	CurSum=MaxSum=0;	st=ed=0;	tmp=0;	for(i=0;i<n;i++)	{		CurSum+=a[i];		if(CurSum>MaxSum)		{			MaxSum=CurSum;			st=tmp;			ed=i;		}		else if(CurSum<0)		{			CurSum=0;			tmp=i+1;		}	}	if(CurSum==0)	{		if(st==0&&ed==n-1)			printf("0 0 0/n");		else			printf("%d %d %d/n",MaxSum,st,ed);	}	else	{		printf("%d %d %d/n",MaxSum,st,ed);	}}int main(){//	freopen("D://in.txt","r",stdin);		int i,n;	while(scanf("%d",&n)!=EOF&&n)	{		for(i=0;i<n;i++)		{			scanf("%d",&a[i]);		}		MaxSubsequenceSum(a,n);	}	return 0;}