---
title: "最长连续子序列"
created: 2025-11-28
tags:
  - 算法
---

# 最长连续子序列

## 题目 最长连续子序列

![[image-90b27994.png]]

## 思路分析

![[image-6f5c70e2.png]]

题意转换为找出一段数 它们的平均值大于100

![[image-9a8d0e79.png]]

关于平均数的技巧 之前 最佳牛围栏 里有遇到过

尝试把每个数都减去平均数

这样就可以从 判断一个分式是否大于某数 转换为 判断一段加法是否大于0的问题

![[image-62b18585.png]]

对一段数进行操作 显然是前缀和问题

将他们再转变成s[r]-s[l-1]的问题

![[image-eb89c183.png]]

那么再分析一下 就可以变成找s[r]左边的一个小于它的数

可以联想到单调栈

但是单调栈找的是最近的一个 并不符合我们要找最长（最左边的那个小于s[r]的数）

也就是说 这里不能随便出栈了 当前数右边的数可能拿它左边的数当答案 而不是确保当前数（栈顶）就是最佳答案 不过相同之处就是 如果出现违背递减的趋势
它还是要被舍弃的（如果这个较大的数能作为答案 那么它左边的数一定能作为更合适的答案 为什么 ？1、更靠左 2、大的都比s[r]小 小的更别说了）
所以 我们要的数还是单调递减的 所以可以沿用单调栈的思想 只不过对出栈逻辑做了一些变动（所以单减的都入栈）

![[image-1786ea57.png]]

现在问题变成了这样 栈顶是最近的一个小于s[r]的数 但不一定是最左边的

而那个答案一定在我们的单调栈中

那么 就可以用二分在单调栈中找到那个最左的小于s[r]的数的下标

（为什么要先单调栈再二分 而不直接二分——原序列并不具有二段性和单调性 单调栈构造出了一个单减的答案区间 构造出了二段性 这样才能用二分）

这里的二分也有所变动

因为之前做的都是单增的二分 现在变成了单减 mid逻辑有些相反

来分析一下

![[image-078b475e.png]]

找的是小于的数 不包含等于

所以区间划分成≥,<

答案取的是右区间的最左的数

若取一个mid 使得小了 说明答案应该在左边 所以r=mid

这样一来 check条件 和模板就都确定了

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e6+10;

LL s[N];//小技巧：如果最后一个数据没过 很有可能是爆int了

int stk[N];

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++){

        int x;cin>>x;

        s[i]=s[i-1]+x-100;

    }

    int top=0;

    int res=0;

    stk[++top]=0;

    for(int i=1;i<=n;i++){

        if(s[i]<s[stk[top]])

            stk[++top]=i;

        else if(s[i]>s[stk[top]]){

            int l=1,r=top;

            while(l<r){

                int mid=l+r>>1;

                if(s[stk[mid]]<s[i])

                    r=mid;

                else

                    l=mid+1;

            }

            res=max(res,i-stk[r]);

        }

    }

    cout<<res<<endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[最大矩形|最大矩形]] 🏠 [[00-刷题理模型]] ➡️ [[直方图中最大的矩形|直方图中最大的矩形]]