P1115 最大子段和(在线处理)

1.描述：

给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

2. 输入：

第一行是一个整数，表示序列的长度 n。

第二行有 n个整数，第 i 个整数表示序列的第 i 个数字 ai

3.输出：

输出一行一个整数表示答案。

4.样例输入：

7
2 -4 3 -1 2 -4 3

5.样例输出：

4

6.题目大意：

求最大子段和

7.思路

在线处理：

首先说最大子列和为非负的一个性质

如果整数序列 的 最大子列和为 那么必定有

对任意的 成立

我对这个性质的理解就是，如果从头开始截取任一段和为负数，那么就与初始条件这是 最大子列 矛盾，这一段是负数我们完全可以不要它。(也就是说，最大子列 前面的元素和一定是负的，这样才被舍弃掉了)我们可以用这个性质进行在线处理，只要当前子列和为负，我们舍弃这一部分即可，不断比较求出一个最大的子列和

当然我们不能忽略一个特殊情况，就是最大子列和为负的情况，只有一个情况会使最大子列和为负，那就是整数序列中所有元素都是负数，这时它的最大子列中肯定也只有一个元素，就是所有负数里最小的那个元素，这对我们这个算法也没影响，每累加一次子列和就进行一次打擂台，进行一次清空，结果就是那个最大的负数，答案也正确，注意把最开始打擂台的数设成一个非常小的数。

8.代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int n;
int a;
ll sum;
ll max1=-1e9+10;
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    scanf("%d",&a);
    sum+=a;//求子列和
    max1=max(sum,max1);//打擂台比较
    if(sum<0) sum=0;//子列和为负就清空
  }
  cout<<max1;
}