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

題目描述

給定 K 個(gè)整數(shù)的序列{ N1,  N2,  ..., NK } ，其任意連續(xù)子序列可表示為{ Ni, Ni+1,...,Nj} ，其中1 <= i<= j <= K。最大連續(xù)子序列是所有連續(xù)子序列中元素和最大的一個(gè)，例如給定序列{ -2, 11, -4, 13, -5, -2 } ，其最大連續(xù)子序列為{ 11, -4, 13 } ，最大和為20。編寫(xiě)程序得到其中最大子序列的和并輸出該子序列的第一個(gè)和最后一個(gè)元素的下標(biāo)。

輸入

測(cè)試輸入包含若干測(cè)試用例，每個(gè)測(cè)試用例占2 行，第 1 行給出正整數(shù) K( <100000) ，第 2 行給出 K 個(gè)整數(shù)，每個(gè)整數(shù)的范圍-10000至10000 ，中間用空格分隔。當(dāng)K 為0 時(shí)，輸入結(jié)束，該用例不被處理。

輸出

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

樣例輸入

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
提示
中南大學(xué)計(jì)算機(jī)&軟件復(fù)試QQ群552889929
來(lái)源
2014年中南大學(xué)研究生復(fù)試機(jī)試題
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;}