题目描述

给出一个长度为 n ( n <= ${10}^5$ ) 的序列，求连续子段的最大值。

比如说 2 3 -4 5 的最大子段和是 6 。

而 2 3 -6 7 的最大子段和为 7 。

输入格式

第 1 行一个数 n，范围 [1,1000]；

第 2 行 n 整数，范围 [-10000,10000]；

输出格式

一个整数，最大和。

样例

7
5 4 3 -15 -12 11 2

13

程序填空

#include<bits/stdc++.h>
using namespace std;
int s[1001];
int main()
{
	int n,i,j,ans=-100000000,t;
	
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		cin>>t;
		s[i] = s[i-1] + t;
	}
	
	int minsum=0; //minsum用来记录从下标1到i-1的最小前缀和，前缀和s[i]减去1到i-1的最小前缀和，就是1到i的最大子段和 
	
	for(i=1;i<=n;i++)
	{
		//根据最小前缀和计算从1到i的最大前缀和 
		if( 填空(1) >ans)
			ans = 填空(2);
		
		//刷新1到i的最小前缀和，为下一轮循环做准备 
		if( 填空(3) )
			minsum=s[i];
	}
	//循环结束，ans内存放的就是从1到n的最大子段和 
	
	printf("%d",ans);

	return 0;
}

填空1：{{ input(1) }}

填空2：{{ input(2) }}

填空3：{{ input(3) }}