P1115 最大子段和

题目描述

给出一个长度为 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. 该元素与之前的连续区间加起来的和还没有这个元素本身大

如果是情况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;
}