题目描述

有 $n$ 个数，要你从中找出一段连续的一段（在术语上，这连续一段称为这 $n$ 个数的子段），使得这个子段的和最大。

补充说明： 如果每个数都是非负数，那么最大子段和一定就是 $n$ 个数全部相加（$n$ 个数本身也是自己的子段，这是一种特殊情况）。当前问题之所以是难题，是因为这 $n$ 个数里面有负数，把全部数加起来未必能使得和最大。

输入格式
第一行 $1$ 个正整数：$n$。
第二行 $n$ 个 正整数 $a_i$

数据范围

$1 \le n \le 100000$

$-10000 \le a_i \le 10000$

输出格式

一个整数，最大子段和。

样例

6
-1 2 -3 3 4 -10

7

完善程序

#include<bits/stdc++.h>
using namespace std;
int x[100001],ans[100001];
int main()
{
	int n,i,t;
	
	scanf("%d",&n);

	for(i=1;i<=n;i++) scanf("%d",&x[i]);

	ans[1] = x[1]; // 有可能全部 x[i] 都是负数的
	for(i=2;i<=n;i++)
	{
		if(ans[i-1]>0)
			ans[i] = 填空(1) ;
		else
			ans[i] = 填空(2);
	}

	int maxsum=-100000000;
	for(i=1;i<=n;i++)
		maxsum = max(maxsum,填空(3));	

	printf("%d",填空(4));

	return 0;
}

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

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

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

填空(4) :{{ input(4) }}