首页 > 代码库 > hdu3415：最大k子段和，单调队列
hdu3415：最大k子段和，单调队列
题目大意：
给定长度为n的数组，求出最大的区间和，其中区间长度在[1,k]之间
分析：
学动态规划的时候我们会遇到一个经典问题
最大子段和，这个题跟最大子段和很类似 不同的是区间的长度有限制，无法用原算法解决
转换思路
区间[i,j]的和就是ans=sum(j)-sum(i-1) （ j - i <=k）
那么对于每个j 我们肯定希望sum(i-1)最小，所以我们只需要对sum(i-1)维护一个单调队列，然后依次增加 j
同时将单调队列中不满足( j - i <k)的元素出队即可
代码：
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define maxn 10000010typedef struct Node{ int val; int num;}node;typedef struct dqueue{ node q[maxn]; int l,r; void ini() { l=0; r=0; } node front() { return q[l]; } node pop() { l++; return q[l-1]; } void push(node x) { if(r==l) { q[r++]=x; return; } if(x.val<q[l].val) { r=l; q[r++]=x; return; } while(r>=1&&(x.val<q[r-1].val)) { r--; } q[r++]=x; }}Dqueue;int a[200020];int sum[200020];Dqueue q;int main(){ int n,k,T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); sum[0]=0; for(int i=1;i<=n;i++) { scanf("%d",a+i); } memcpy(a+n+1,a+1,n*sizeof(int)); for(int i=1;i<=2*n;i++) { sum[i]=sum[i-1]+a[i]; } node x; node tmp; int t=0; q.ini(); int ans=-10000; int l,r; for(int i=1;i<=2*n;i++) { x.val=sum[i-1]; x.num=i-1; q.push(x); while(1) { tmp=q.front(); if(i-tmp.num>k) { q.pop(); } else { break; } } if(sum[i]-tmp.val>ans) { ans=sum[i]-tmp.val; l=tmp.num+1; r=i; continue; } } if(r>n) { r-=n; } printf("%d %d %d\n",ans,l,r); } return 0;}
hdu3415：最大k子段和，单调队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。