历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 135. 【算法提高课】最大子序和（单调队列优化DP）原题链接简单

作者：

incra , 2023-01-18 10:15:37 , 所有人可见 , 阅读 821

15

1

<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

输入一个长度为 $n$ 的整数序列，从中找出一段长度不超过 $m$ 的连续子序列，使得子序列中所有数的和最大。

注意： 子序列的长度至少是 $1$。

输入格式

第一行输入两个整数 $n,m$。

第二行输入 $n$ 个数，代表长度为 $n$ 的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数，代表该序列的最大子序和。

数据范围

$1 \\le n,m \\le 300000$

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

思路

闫氏$\text{DP}$分析法：
状态表示：$f_{i}$

集合：以$i$为结尾的最大子序和
属性：$\max$

状态计算：

$f_i=\max\limits_{j\in[1,i - 1]}\{s_i-s_j\}$
变化一下式子，得$f_i=s_i-\min\limits_{j\in[0,i-1]}\{s_j\}$
所以很明显我们可以维护一个$1\sim i-1$的单调队列来优化

时间复杂度

单调队列时间复杂度为$O(n)$，总时间复杂度为$O(n)$

代码

#include <iostream>
#include <deque>
using namespace std;
typedef long long LL;
const int N = 300010;
int n,m;
int a[N];
LL s[N];
deque <int> q;
int main () {
    scanf ("%d%d",&n,&m);
    for (int i = 1;i <= n;i++) {
        scanf ("%d",&a[i]);
        s[i] = s[i - 1] + a[i];
    }
    LL ans = -1e14;
    q.push_back (0);
    for (int i = 1;i <= n;i++) {
        while (q.size () && i - q.front () > m) q.pop_front ();
        ans = max (ans,s[i] - s[q.front ()]);
        while (q.size () && s[q.back ()] >= s[i]) q.pop_back ();
        q.push_back (i);
    }
    printf ("%d\n",ans);
    return 0;
}

9 评论

mhmh 2023-03-22 12:48

### tt = 0时 AC

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 300010,INF = 1e9;

//单调队列的队列里存的是下标，这样才好判断出队
int q[N];
int a[N],s[N];
int n,m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }

    int hh = 0, tt = 0;
    int res = -INF;
    for(int i = 1; i <= n; i ++)
    {
        if(q[hh] < i - m) hh ++;
        res = max(res, s[i] - s[q[hh]]);
        while(hh <= tt && s[q[tt]] > s[i]) tt--;
        q[++ tt] = i;
    }

    cout << res << endl;

    return 0;
}

mhmh 2023-03-22 12:48

### tt = -1时 WA

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 300010,INF = 1e9;

//单调队列的队列里存的是下标，这样才好判断出队
int q[N];
int a[N],s[N];
int n,m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }

    int hh = 0, tt = -1;
    int res = -INF;
    for(int i = 1; i <= n; i ++)
    {
        if(q[hh] < i - m) hh ++;
        res = max(res, s[i] - s[q[hh]]);
        while(hh <= tt && s[q[tt]] > s[i]) tt--;
        q[++ tt] = i;
    }

    cout << res << endl;

    return 0;
}