---
title: "最大子序和"
created: 2025-11-28
tags:
  - 算法
---

# 最大子序和

## 题目 [最大子序和](https://www.acwing.com/problem/content/description/137/)

![[image-204e7121.png]]

## 思路分析

首先很容易想到前缀和

![[image-a3a8821a.png]]

问题转变成对于每个r找一个窗口中的最小的l-1

可以挖掘出一些性质

如果-2加入 那它左边的1就绝对不会是答案 因为1本身就在左边 会先出队 所以1可以删除

而-2右边的3有可能作为答案 因为-2在左边 它会先从窗口划出去

所以这个队列里的数应该是单调递增的

我们要的答案就是队头的那个最小的数

单调队列 模版中的找最小值

![[image-3ec719b8.png]]

注意一个问题 5的要找的答案应该是那个-2 （s[r]-s[l-1]）

窗口在5加入之前得出答案 而不是5加入后得到答案

所以先求res再插入5 对队列做维护

## 代码实现

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

using namespace std;

typedef long long LL;

const int N=300010;

int q[N];

LL s[N];

int n,m;

int main()

{

    cin>>n>>m;

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

        int x;

        cin>>x;

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

    }

    int hh=0,tt=0;

    q[0]=0;

    LL res=INT_MIN;

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

        if(hh<=tt && i-q[hh]>m)

            hh++;

        //注意这个位置 当前数的左边最小值 应该是不包含该数的左边m个数里找（在队头） 所以在插入之前更新答案

        res=max(s[i]-s[q[hh]],res);

        while(hh<=tt && s[i]<=s[q[tt]])

            tt--;

        q[++tt]=i;

    }

    cout<<res<<endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[子矩阵|子矩阵]] 🏠 [[00-刷题理模型]] ➡️ [[滑动窗口的最大值|滑动窗口的最大值]]