nyoj 44 子串和

nyoj 44 子串和

子串和

描述

給定一整型數列{a₁,a₂...,a_n}，找出連續非空子串{a_x,a_x+1,...,a_y}，使得該子序列的和最大，其中，1<=x<=y<=n。

輸入

第一行是一個整數N(N<=10)表示測試數據的組數）
每組測試數據的第一行是一個整數n表示序列中共有n個整數，隨後的一行裡有n個整數I(-100= 輸出

對於每組測試數據輸出和最大的連續子串的和。

樣例輸入

1
5
1 2 -1 3 -2

樣例輸出

5

#include
int main()
{
	int N;
	scanf("%d",&N);
	while(N--)
	{
		int max,n,i,sum;
		scanf("%d",&n);
        scanf("%d",&sum);
		max=sum;
		n=n-1;
		while(n--)
		{
			scanf("%d",&i);
			if(sum>=0)
				sum+=i;
			else
				sum=i;
			if(sum>max)
				max=sum;
		}
		printf("%d\n",sum);
	}

	return 0;
}