Max Sum of Max-K-sub-sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5084 Accepted Submission(s): 1842
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
Recommend
lcy
题目大意：T 组数据，求 n 个数 连续子串的最大和是多少，子串要求长度不超过 k，以及这是个环形，如果多解，满足起点be最小，其次终点en最小
解题思路：枚举每个起点be，终点en一定是在 be<=en<=be+k-1 这个范围内，所以求这个范围内的连续最长和即可，可以用 sum[en] -sum[be-1] ，其中sum[x]表示前x个数的和，所以即选出 be<=en<=be+k-1这个范围内最大sum[i]，用线段树过了，但是rmq算法超时，郁闷！
线段树算法，AC
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int maxn=200010;
int d[maxn],sum[maxn],n,k,mx,mn;
struct node{
int l,r,minc,maxc;
}a[4*maxn];
void input(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&d[i]);
d[i+n]=d[i];
}
sum[0]=0;
for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+d[i];
}
void build(int l,int r,int k){
a[k].l=l;
a[k].r=r;
if(l<r){
int mid=(l+r)/2;
build(l,mid,2*k);
build(mid+1,r,2*k+1);
a[k].maxc=max(a[2*k].maxc,a[2*k+1].maxc);
a[k].minc=min(a[2*k].minc,a[2*k+1].minc);
}else{
a[k].maxc=sum[l];
a[k].minc=sum[l];
}
}
void query(int l,int r,int k){
if(l<=a[k].l && a[k].r<=r){
//cout<<a[k].maxc<<" "<<a[k].minc<<endl;
mx=max(mx,a[k].maxc);
mn=min(mn,a[k].minc);
}else{
int mid=(a[k].l+a[k].r)/2;
if(r<=mid) query(l,r,2*k);
else if(l>=mid+1) query(l,r,2*k+1);
else{
query(l,mid,2*k);
query(mid+1,r,2*k+1);
}
}
}
void computing(){
build(0,2*n,1);
int ans=-(1<<30),be=1,en=1;
for(int i=1;i<=n;i++){
mx=-(1<<30);
query(i,i+k-1,1);
if(mx-sum[i-1]>ans){
ans=mx-sum[i-1];
be=i;
}
}
for(int i=be;i<=be+k-1;i++){
if(sum[i]-sum[be-1]==ans){
en=i;
break;
}
}
printf("%d %d %d\n",ans,be>n?be-n:be,en>n?en-n:en);
}
int main(){
int t;
scanf("%d",&t);
while(t-- >0){
input();
computing();
}
return 0;
}
rmq算法，超时，郁闷中
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int maxn=300005*2;
int maxsum[maxn][20],minsum[maxn][20],flog[maxn],d[maxn],sum[maxn],n,k;
void ini(){
int r=2,cnt=0;
for(int i=1;i<maxn;i++){
if(i<r) flog[i]=cnt;
else{
flog[i]=++cnt;
r=r<<1;
}
}
}
void input(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&d[i]);
d[i+n]=d[i];
}
}
void getrmq(){
for(int i=1;i<=2*n;i++){
sum[i]=sum[i-1]+d[i];
maxsum[i][0]=sum[i];
minsum[i][0]=sum[i];
}
for(int j=1;j<=flog[2*n];j++)
for(int i=1;i<=2*n;i++){
if(i+(1<<j)-1<=2*n){
maxsum[i][j]=max(maxsum[i][j-1],maxsum[i+(1<<(j-1))][j-1]);
minsum[i][j]=min(minsum[i][j-1],minsum[i+(1<<(j-1))][j-1]);
}
}
}
void computing(){
getrmq();
int ans=-(1<<30),be=1,en=1,l,r,x,tmp;
for(int i=1;i<=n;i++){
l=i,r=i-1+k,x=flog[r-l+1];
tmp=max(maxsum[l][x],maxsum[r-(1<<x)+1][x]);
if(tmp-sum[i-1]>ans){
ans=tmp-sum[i-1];
be=i;
}
}
for(int i=be;i<=be+k-1;i++){
if(sum[i]-sum[be-1]==ans){
en=i;
break;
}
}
printf("%d %d %d\n",ans,be>n?be-n:be,en>n?en-n:en);
}
int main(){
ini();
int t;
scanf("%d",&t);
while(t-- >0){
input();
computing();
}
return 0;
}
