5804: 最大子序和（单调队列）

发布时间：2020-12-15 01:57:08 所属栏目：Java 来源：网络整理

导读：5804: 最大子序和 ? 时间限制(普通/Java):1000MS/3000MS ? ? 内存限制:65536KByte 总提交: 86 ? ? ? ?? ? 测试通过:32 描述 ? 输入一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。例如 1，-3,5,1，-2,3 当m=4时，S=5+1-2+

　　　　　　　　　　　　　　5804: 最大子序和?

时间限制(普通/Java):1000MS/3000MS ? ? 内存限制:65536KByte
总提交: 86 ? ? ? ?? ? 测试通过:32

描述

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

例如 1，-3,5,1，-2,3

当m=4时，S=5+1-2+3=7
当m=2或m=3时，S=5+1=6

输入

第一行两个数n,m（n,m<=300000）
第二行有n个数，要求在n个数找到最大子序和

输出

一个数，数出他们的最大子序和

样例输入

样例输出

题目来源

TZOJ

解题思路：维护一个单调递增的前缀和（队尾大，对头小总和才大）维护过程中更新最大值！

 1 #include <iostream>
 2 #include <cstring>
 3 #include <deque>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 typedef long long ll;
 8 int n,m;
 9 const int N=300005;
10 ll dp[N],q[N];
11 
12 int main(){
13     ios::sync_with_stdio(false);
14     cin>>n>>m;
15     for(int i=1,d;i<=n;i++){
16         cin>>d;
17         dp[i]=dp[i-1]+d;
18     }
19     int left=1,right=1;
20     q[1]=0;  ///队列里存放位置
21     ll res=-0x3f3f3f3f;
22     for(int i=1;i<=n;i++){
23         while(left<=right&&i-m>q[left]) left++;
24         res=max(res,dp[i]-dp[q[left]]);
25         while(left<=right&&dp[i]<=dp[q[right]]) right--;
26         q[++right]=i;
27     }
28     cout << res << endl;
29     return 0;
30 }

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!