题目描述

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

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

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

数据范围
1 <= N <= 100000
-10000 <= $a_i$ <= 10000

输出格式
一个整数，最大子段和。

样例

6
-1 2 -3 3 4 -10

7

算法分析

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

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

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

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

可以用 前缀和 算法来帮我们实现第 1 步。以第 i 个数为结尾，也就是说第 i 个数字一定要选，而且是子段里面的最后一个数；它前面可以再选若干个连续的数字。从第 1 个到 第 i 个数之和是确定的，就是前缀和的 $s_i$。假设 从第 j (j <i) 个数开始到第 i 个数的和就是 $x_i$，那么 ${len}_i = s_i - s_{j-1}$，这是前缀和的公式。 $s_i$ 是一个固定值，为了让 $x_i$ 最大，那么就是需要让 $s_{j-1}$ 最小。

所以，问题进一步转换，对于任意一个 i 而言，要求最小的 $s_j$ ( j < i )。这个可以用一个动态变化的变量来获得：

• 对于 i=1 的时候：最小的 $s_i$ 就是 $s_0$ 了，其实就是 0 ，不存在多种情况的选择，我们把 0 赋值给 minsum

• 对于 i=2 的时候：最小的 $s_i$ 无非就是 min ( minsum, $s_1$ )，我们把这个结果又赋值给 minsum

• 对于后面的 i，最小的 $s_i$ 无非就是 min ( minsum, $s_{j-1}$ )，我们把这个结果又赋值给 minsum

程序填空

#include<bits/stdc++.h>
using namespace std;
int x[100001],s[100001];
int main()
{
	int n,t,i,minsum=0,ans=-1000000000;

	scanf("%d",&n);
	
	for(i=1;i<=n;i++)
	{
		scanf("%d",&t);

		s[i] = 填空(1) +t; //计算前缀和 

		minsum = min(minsum,填空(2)); //计算最小前缀和 
		
		x[i] = 填空(3) - minsum;
		
	}

	//枚举全部情况，以任意一个数为结尾的最大字段和，得到的就是任意情况下的最大字段和。 
	for(i=1;i<=n;i++)
		ans = max(ans, 填空(4) ); 
			
	printf("%d",ans);	

	return 0;
}

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

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

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

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