题目描述

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

输入格式

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

第二行有 n 个整数,第 i 个整数表示序列的第 i 个数字 aia_i

输出格式

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

输入输出样例

输入 #1

7
2 -4 3 -1 2 -4 3

输出 #1

4

说明/提示

样例 1 解释

选取 [3,5][3, 5] 子段 {3,1,2}\{3, -1, 2\},其和为 4。

数据规模与约定

  • 对于 40% 的数据,保证 n2×103n \leq 2 \times 10^3
  • 对于 100% 的数据,保证 1n2×105104ai1041 \leq n \leq 2 \times 10^5,-10^4 \leq a_i \leq 10^4

题目分析

尺取法的本质是对连续区间的维护,被维护的区间符合某种条件。右指针相当于把元素加入到这个区间,左指针相当于把元素从区间内去除。除了之前题目中的双指针,骑士也能够用队列来进行处理,又或者是具有相似概念的东西。

仔细阅读题目,可发现题目要求的是连续且非空的最大子段和。

若用暴力方式处理复杂度为O(n3)O(n^3),根据数据范围明显不可取。此时,可发现又是一个对连续区间的维护问题,那么我们尝试从其他的角度进行思考。

该区间元素必须连续,那么当碰见一个新的元素,无非出现两种情况:

  1. 该元素与之前的连续区间加起来的和比较大
  2. 该元素与之前的连续区间加起来的和还没有这个元素本身大

如果是情况1,那么连续区间总和就加上新增元素。而如果是情况2,则将该元素作为新的连续区间总和。在过程中再不断更新最大连续区间和即可。

由于只需遍历每个元素一次,时间复杂度为O(n)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;
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)