题目描述
给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数，表示序列的长度 n。
第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 aia_iai。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入 #1
代码语言：javascript复制7
2 -4 3 -1 2 -4 3输出 #1
代码语言：javascript复制4说明/提示
样例 1 解释
选取 [3,5] 子段 {3,−1,2}，其和为 4。
数据规模与约定
- 对于 40% 的数据，保证
- 对于 100% 的数据，保证
题目分析
尺取法的本质是对连续区间的维护，被维护的区间符合某种条件。右指针相当于把元素加入到这个区间，左指针相当于把元素从区间内去除。除了之前题目中的双指针，骑士也能够用队列来进行处理，又或者是具有相似概念的东西。
仔细阅读题目，可发现题目要求的是连续且非空的最大子段和。
若用暴力方式处理复杂度为
根据数据范围明显不可取。此时，可发现又是一个对连续区间的维护问题，那么我们尝试从其他的角度进行思考。
该区间元素必须连续，那么当碰见一个新的元素，无非出现两种情况：
- 该元素与之前的连续区间加起来的和比较大
- 该元素与之前的连续区间加起来的和还没有这个元素本身大
如果是情况1，那么连续区间总和就加上新增元素。而如果是情况2，则将该元素作为新的连续区间总和。在过程中再不断更新最大连续区间和即可。
由于只需遍历每个元素一次，时间复杂度为O(n)。
代码实现
代码语言：javascript复制#include <iostream>
#include <cstdio>
using namespace std;
int a;
/*
连续序列和
1. 当前元素
2. 和前面的一段组成新序列
*/
int main(){
int n;
int sum=0;//连续序列和
int ans=-1e9;//最大连续序列和
cin>>n;
for(int i=1;i<=n;i ){
cin>>a;
if(sum a<a){//判断是a与前面的连续序列加起来大还是单独一个元素更大
sum=a;//单独的元素更大
}else{
sum =a;//加起来更大
}
ans=max(ans,sum);//更新过程中的最大连续序列和
}
cout<<ans;//输出答案
return 0;
}Q.E.D.
