题目描述
给出一个长度为 n 的序列 a,选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数,表示序列的长度 n。
第二行有 n 个整数,第 i 个整数表示序列的第 i 个数字 $a_i$。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入 #1
7
2 -4 3 -1 2 -4 3
输出 #1
4
说明/提示
样例 1 解释
选取 $[3, 5]$ 子段 $\{3, -1, 2\}$,其和为 4。
数据规模与约定
- 对于 40% 的数据,保证 $n \leq 2 \times 10^3$。
- 对于 100% 的数据,保证 $1 \leq n \leq 2 \times 10^5,-10^4 \leq a_i \leq 10^4$。
题目分析
尺取法的本质是对连续区间的维护,被维护的区间符合某种条件。右指针相当于把元素加入到这个区间,左指针相当于把元素从区间内去除。除了之前题目中的双指针,骑士也能够用队列来进行处理,又或者是具有相似概念的东西。
仔细阅读题目,可发现题目要求的是连续且非空的最大子段和。
若用暴力方式处理复杂度为$O(n^3)$,根据数据范围明显不可取。此时,可发现又是一个对连续区间的维护问题,那么我们尝试从其他的角度进行思考。
该区间元素必须连续,那么当碰见一个新的元素,无非出现两种情况:
- 该元素与之前的连续区间加起来的和比较大
- 该元素与之前的连续区间加起来的和还没有这个元素本身大
如果是情况1,那么连续区间总和就加上新增元素。而如果是情况2,则将该元素作为新的连续区间总和。在过程中再不断更新最大连续区间和即可。
由于只需遍历每个元素一次,时间复杂度为$O(n)$。
代码实现
#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;
}
2 条评论
《李子柒古香古食全集》记录片高清在线免费观看:https://www.jgz518.com/xingkong/90885.html
你的文章让我感受到了艺术的魅力,谢谢! http://www.55baobei.com/LInx8xUK28.html