首页 > 其他 > 详细

最大子序和

时间:2019-02-11 22:19:02      阅读:30      评论:0      收藏:0      [点我收藏+]

标签:etc   per   stat   内存   getchar()   define   href   creator   超过   

问题 E: 最大子序和

时间限制: 1 Sec  内存限制: 128 MB
提交: 138  解决: 43
[提交] [状态] [讨论版] [命题人:admin]

题目描述

输入一个长度为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个数找到最大子序和

 

输出

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

 

样例输入

6 4
1 -3 5 1 -2 3

样例输出

7
思路:单调队列模板题,维护m个数以内的单调递增前缀和,dp[i]=sum[i]-min(sum[j])(j<=i&&j>i-m)可以直接记录ans,不用开dp数组。
#include<iostream>
#include<cstring>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i <= (b); ++ i)
#define REP(j, a, b) for(int j = (a); j <= (b); ++ j)
#define PER(i, a, b) for(int i = (a); i >= (b); -- i)
using namespace std;
const int maxn = 3e5+10;
template <class T>
inline void rd(T &ret){
    char c;
    ret = 0;
    while ((c = getchar()) < 0 || c > 9);
    while (c >= 0 && c <= 9){
        ret = ret * 10 + (c - 0), c = getchar();
    }
}
int n,m,ans;
int p[maxn],s[maxn],que[maxn];
int main() {
       int h=1,t=1;
       rd(n),rd(m);
       REP(i, 1, n){
           cin>>p[i];
           s[i]=s[i-1]+p[i];
       }
       REP(i, 1, n){
           while(i-que[h]>m)h++;
           ans=max(ans,s[i]-s[que[h]]);
           while(h<=t&&s[que[t]]>s[i])t--;
           que[++t]=i;
       }
       cout<<ans<<endl;
}

 

 

最大子序和

标签:etc   per   stat   内存   getchar()   define   href   creator   超过   

原文:https://www.cnblogs.com/czy-power/p/10363272.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号