题目描述

有 $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

算法分析

分两步去获得题目的答案：

1. 计算以第 i 个数为结尾的最大字段和，把这个信息存放如 x[ ] 数组

2. 在 1 的基础上，枚举以每一个数为结尾数的情况，就可以得到全局的 最大字段和。

第 2 步很容易，第 1 步有点难，而且有不同的方法是。

可以用 连续性分析 算法来帮我们实现第 1 步。以第 i 个数为结尾的字段可以分成 2 大类：

• 只有 $a_i$，不包含前面的数字

• 除了 $a_i$ 之外，前面还有一些数字。

我们进一步分析，如果是属于上述的第二种情况，那么只有当 以 $a_{i-1}$ 为结尾的最大字段和是一个正数 ，否则，为了让 $a_i$ 为结尾的字段和大一点，不应该前面加上一截和为负数的段落。

程序填空

#include<bits/stdc++.h>
using namespace std;
int x[100001],t;
int main()
{
	int n,i,t;
	int ans=-100000000;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&t); //原来的数列不需要保存到一个数组里，因为这个数列只访问一次 
		
		if(x[i-1]>0)
			x[i] = 填空(1) + t; //接上 a[i-1]结尾的最大字段和 
		else
			x[i] = 填空(2);   //只包含自己 
	}

	//枚举，刷最大值，获得任何一个数结尾的最大字段和 
	for(i=1;i<=n;i++)
		ans = max(ans,x[i]);	

	printf("%d",ans);

	return 0;
}

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

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

上面的程序，还可以写成下面这样：

#include<bits/stdc++.h>
using namespace std;
int x[100001],t;
int main()
{
	int n,i,t;
	int ans=-100000000;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&t); //原来的数列不需要保存到一个数组里，因为这个数列只访问一次 
		x[i] = max(t,x[i-1]+t);
	}


	//枚举，刷最大值，获得任何一个数结尾的最大字段和 
	for(i=1;i<=n;i++)
		ans = max(ans,x[i]);	

	printf("%d",ans);

	return 0;
}