首页 > 代码库 > hdu 3415 Max Sum of Max-K-sub-sequence
hdu 3415 Max Sum of Max-K-sub-sequence
Problem Description
Given a circle sequence A[1],A[2],A[3]......A[n]. Circle sequence means the left neighbour of A[1] is A[n] , and the right neighbour of A[n] is A[1].
Now your job is to calculate the max sum of a Max-K-sub-sequence. Max-K-sub-sequence means a continuous non-empty sub-sequence which length not exceed K.
Now your job is to calculate the max sum of a Max-K-sub-sequence. Max-K-sub-sequence means a continuous non-empty sub-sequence which length not exceed K.
Input
The first line of the input contains an integer T(1<=T<=100) which means the number of test cases.
Then T lines follow, each line starts with two integers N , K(1<=N<=100000 , 1<=K<=N), then N integers followed(all the integers are between -1000 and 1000).
Then T lines follow, each line starts with two integers N , K(1<=N<=100000 , 1<=K<=N), then N integers followed(all the integers are between -1000 and 1000).
Output
For each test case, you should output a line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the minimum start position, if still more than one , output the minimum length of them.
Sample Input
4 6 3 6 -1 2 -6 5 -5 6 4 6 -1 2 -6 5 -5 6 3-1 2 -6 5 -5 6 6 6-1 -1 -1 -1 -1 -1
Sample Output
7 1 3 7 1 3 7 6 2-1 1 1
Author
shǎ崽@HDU
Source
HDOJ Monthly Contest – 2010.06.05
单调队列的应用
#include<map> #include<set> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 0x0f0f0f0f using namespace std; const int maxn=100000+10; int sum[maxn*2],a[maxn]; 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]); sum[i]=sum[i-1]+a[i]; } for (int i=1;i<=n;i++) sum[n+i]=sum[n+i-1]+a[i]; int start,end,ans=-99999999; deque<int>q; //q.push_back(0); for (int i=1;i<=n+k-1;i++) { while(!q.empty() && sum[i-1]<sum[q.back()]) q.pop_back(); while(!q.empty() && q.front()<i-k) q.pop_front(); q.push_back(i-1); if (sum[i]-sum[q.front()]>ans) { ans=sum[i]-sum[q.front()]; start=q.front()+1; end=i; } } if (end!=n) end%=n; printf("%d %d %d\n",ans,start,end); } return 0; }
作者 chensunrise
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。