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.

 

 

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).

 

 

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 
     
      #include 
      
       #include 
       
        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
        
         =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 
     
      #include 
      
       #include 
       
        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
        
         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;}