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; }
