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

蔚落 2021-12-13 04:02 267阅读 0赞

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

对于这个题， 可以先确定右端i，那么问题就变成了找到j （i- j <=m），同时sum\[j\]是sum\[i-m\]到sum\[i\]里面最小的值。那么问题就变为了以每个结点为右端点时，找到最优的左端点。  
故，可能的最优集合一定是一个“下标位置递增，对应的前缀和S的值也递增”的序列。这是一个单调队列。

#include"stdio.h"
    #include"string.h"
    #include"deque"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    deque<ll> Q;
    ll sum[300100];
    ll n,m;
    
    int main()
    {
        sum[0] = 0;
        scanf("%lld%lld",&n,&m);
        for(int i = 1; i <= n; i ++)
        {
            scanf("%lld",&sum[i]);
            sum[i] += sum[i - 1];
        }
        ll ans = 0;
        Q.push_back(0);
        for(int i = 1; i <= n; i ++)
        {
            if(!Q.empty() && i - Q.front() > m)
                Q.pop_front();
            ans = max(ans,sum[i] - sum[(int)Q.front()]);
            while(!Q.empty() && sum[i] <= sum[(int)Q.back()])
                Q.pop_back();
            Q.push_back(i);
        }
        printf("%lld\n",ans);
    }

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

发表评论取消回复

表情：

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

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

相关阅读

相关最大子序和

最大子序和 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 赞/ 134 阅读

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

[\[算法竞赛进阶指南\]最大子序和][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 赞/ 268 阅读

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

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

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