普及- 洛谷 P1115 最大子段和
读题可知需要在一段一维数组中寻找一段唯一的区间，使区间内的数和最大，即寻找和最大区间
可以想到前缀和的算法
假设输入数组 a[n]
则前缀和数组 b[n]=b[n-1]+a[n]
那么从什么时候开始的一段区间才能使区间内的数和最大?
从前缀和数组逐步来判断这一条件
从 b[1] 开始，当 b[i] 即a的前 i 项前缀和 小于 a[i] 时，那么选取前 i 项 a 的前缀和还不如只从 a[i]开始选
这样就可以得出什么时候开始的一段区间才能使区间内的数和最大，即从 a 的第 i 项开始
将 b[i] 更新为 a[i]，继续逐步判断，直到再次找到 b[j] 即a 从 a[i] ~ a[j] 的前缀和 小于 a[j] 时
我们可以说选到 a[j] 就足够了，此时就得到了一个在 a 的第 j 项前的一个区间使区间内的数和最大
将 b[j] 更新为 a[j] ，开启下一轮寻找和最大区间的操作
重复如上寻找和最大区间的操作，可以将每个和最大区间存储在一个数组中
这里我们采用一种节省空间的办法：在每次找到和最大区间后，对其进行判断，若是大于前一个和最大区间，则更新和最大区间
核心代码如下：
int a[200010], b[200010];
int main()
{
int n,max1;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (i == 1) max1 = a[i];//初始化和最大区间为第一项
b[i] = max(a[i], b[i - 1] + a[i]);//逐步寻找到边界值，若b[i]<a[i]则更新b[i]为a[i]，否则继续逐步计算前缀和
max1 = max(b[i], max1);//判断是否为最大的 和最大区间
}
printf("%d", max1);
return 0;
}