最大子序和

标签：ll 最大 int res tt leq hh 子序

斜率优化DP

原题链接

题目描述：求长度为n的序列中一段长度不超过m的连续子序列的最大和

一段区间的和可以用前缀和来搞定
状态定义：
f[i]表示以a[i]结尾的长度不超过m的连续子序列最大和
状态转移：

\[f_i=max\{s_i-s_j\}\quad(1\leq i-j\leq m) \]

得到\(j\)的范围：\(i-m\leq j\leq i-1\)
可以得到：\(f_i=s_i-min\{s_j\}\)
也就是求一个窗口内\(s_j\)的最小值，自然想到滑动窗口
具体代码如下：

Code

#include <iostream>
#include <algorithm>

using ll = long long;

const int N = 3e5 + 5;

ll s[N], q[N];

int main() {
    int n, m;
    std::cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        std::cin >> s[i];
        s[i] += s[i - 1];
    }
    
    ll res = -1e18, hh = 0, tt = -1;
    q[ ++ tt] = 0; // 先将下标0放入队列，因为前缀和
    for (int i = 1; i <= n; i ++ ) {
        if (i - m > q[hh]) hh ++ ;
        res = std::max(res, s[i] - s[q[hh]]);
        while (hh <= tt && s[q[tt]] >= s[i]) tt -- ;
        q[ ++ tt] = i;
    }
    
    std::cout << res << '\n';
    return 0;
}

标签：ll,最大,int,res,tt,leq,hh,子序
From： https://www.cnblogs.com/zjh-zjh/p/16711939.html