hdu1231最大连续子序列

如题，求最大连续子序列和

注意的是，全为负的情况比较特殊

直接用1003的代码，改改也就过了

这里用第三组数据演示一下算法的过程。

i	0	1	2	3	4	5
a[i]	5	-8	3	2	5	0

《《maxsum=temsum=5；start=end=0；

i=1

     temsum=5-8=-3；

i=2

     temsum<0;

     start=2;temsum=3;maxsum=5

i=3

     temsum>0;  temsum=3+2=5,maxsum=5,不变。

i=4

    temsum>0;temsum=5+5=10;

    temsum==10>maxsum==5;

    maxsum=10,start=2,end=4;

i=5

    temsum>0;temsum=10+0=10;

    start,end,maxsum 不做修改

所以输出maxsum:10, a[2]:3, a[4]:5

    

#include <iostream>
using namespace std;
int a[100010];
bool flag;
int main()
{
	int n;
	while(scanf("%d",&n))
	{
		if(!n)
			break;
		bool flag=true;
		for(int i =0;i<n;i++)
		{
			scanf("%d",&a[i]);
			if(a[i]>=0)
				flag=false;
		}
		if(flag)
		{
			printf("0 %d %d
",a[0],a[n-1]);
			continue;
		}
		int maxsum=a[0],tempsum=a[0];
		int start=0,end=0, itemp=0;
		for(int i=1;i<n;i++)
		{
			if(tempsum<0)
			{
				tempsum=0;
				itemp=i;
			}
			tempsum+=a[i];
			if(tempsum>maxsum)
			{
				maxsum=tempsum;
				start=itemp;
				end=i;
			}
		}
		printf("%d %d %d
",maxsum,a[start],a[end]);
	}
	return 0;
}