最大子序和（单调队列）

r囧r小猫 2021-10-19 03:58 305阅读 0赞

[https://www.acwing.com/problem/content/137/][https_www.acwing.com_problem_content_137]

我们知道不加长度限制的最大子序列和可以用贪心轻松解决。然而这道题中给子序列增加了一个最大长度为m的限制，那么贪心就不正确了。

首先将区间和转化为前缀和之差，那么\[l，r\]的区间和应该是S\[r\]-S\[l-1\]。那么该问题就转化为找到x，y（x<y且y-x<=m）使得S\[y\]-S\[x\]最大。

如果y固定，那么S\[x\]自然是越小越好，那么如果我们能维护一个单调递增的队列，这个问题就可以解决了。

使用单调队列，依次push编号入队，在每个编号i即将入队时进行一下决策：

1.如果i-队首编号>m，则弹出队首元素。

2.经过1步骤之后，队首元素就是对于i的最优左端点。若队列为空，则i的左端点就是自身。

3.循环弹出S值大于S\[i\]的队尾元素。

4.将i压入队尾。

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <deque>
    using namespace std;
    typedef long long LL;
    deque<LL> dq;
    int n,m;
    LL sum[300010];
    
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%lld",&sum[i]);
        for(int i=1;i<=n;i++) sum[i]=sum[i]+sum[i-1];
        LL ans=-1e18;
        dq.push_back(0);
        for(int i=1;i<=n;i++)
        {
            while(!dq.empty()&&dq.front()<i-m) dq.pop_front();
            if(dq.empty()) ans=max(ans,sum[i]);
            else ans=max(ans,sum[i]-sum[dq.front()]);
            while(!dq.empty()&&sum[dq.back()]>=sum[i]) dq.pop_back();
            dq.push_back(i);
        }
        printf("%lld\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/BakaCirno/p/11297340.html

[https_www.acwing.com_problem_content_137]: https://www.acwing.com/problem/content/137/

发表评论取消回复

表情：

评论列表（有 0 条评论，305人围观）

还没有评论，来说两句吧...

相关阅读

相关最大子序和

最大子序和 1、参考资料 https://leetcode-cn.com/problems/maximum-subarray/ 2、题目要求 > 题目描述

古城微笑少年丶/ 2022年12月05日 10:13/ 0 赞/ 179 阅读

相关 135 最大子序和（单调队列优化）

1. 问题描述：输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。注意：子序列的长度至少是 1。输入格式第一行

谁践踏了优雅/ 2022年08月28日 07:48/ 0 赞/ 133 阅读

相关 [算法竞赛进阶指南]最大子序和(前缀和+单调队列)

[\[算法竞赛进阶指南\]最大子序和][Link 1] Description 输入一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。

偏执的太偏执、/ 2022年04月24日 07:12/ 0 赞/ 170 阅读

相关最大子序和

给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,2,1,-5

妖狐艹你老母/ 2022年04月16日 02:12/ 0 赞/ 202 阅读

相关最大子序和

题目描述给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,2

灰太狼/ 2022年02月26日 04:52/ 0 赞/ 225 阅读

相关最大子序和——最大子矩阵

[LeetCode-最大子序和][LeetCode-] 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:

清疚/ 2022年02月20日 05:52/ 0 赞/ 304 阅读

相关最大子序和

1.暴力解法 O(n^3) class Solution { public: int FindGreatestSumOfSubArray(v

快来打我*/ 2022年02月05日 12:51/ 0 赞/ 231 阅读

相关最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,2,1,-5,4

川长思鸟来/ 2022年01月20日 04:09/ 0 赞/ 247 阅读

相关 AcWing 135. 最大子序和（单调队列）

题目链接：[https://www.acwing.com/problem/content/137/][https_www.acwing.com_problem_content_

蔚落/ 2021年12月13日 04:02/ 0 赞/ 267 阅读

相关最大子序和（单调队列）

[https://www.acwing.com/problem/content/137/][https_www.acwing.com_problem_content_137]

r囧r小猫/ 2021年10月19日 03:58/ 0 赞/ 306 阅读