网易有道资格赛1-最大和子序列

我个NC。。这道题代码量实际上很小而且也不是很triky。。比赛的时候我居然悲剧囧死了。。。。
就是原来的算法,首先由于每个都是非空的那么特判一下正数小于等于2个情况(此时显然取最大的两个)。。然后先算没有跨越环的,设L[x]表示1-x的最大子序列长度,R[x]表示x-n的最大子序列长度,答案很显然就是Max(L[x]+R[x+1])。。。然后如果跨越环了,那么它的对偶问题就是不选的那些肯定不跨越环,一样的DP可以算出来(为了方便把所有值取负就OK了。。)。。两个中的最大值就是答案了。。。。
Code:
#include<cstdio>#include<algorithm>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=50000+10,inf=~0U>>1;int t,n,A[maxn],L[maxn],R[maxn];int Cal(){ L[0]=0; for(int i=1;i<=n;i++) L[i]=max(L[i-1],0)+A[i]; R[n+1]=0; for(int i=n;i>=1;i–) R[i]=max(R[i+1],0)+A[i]; for(int i=1;i<=n;i++)L[i]=max(L[i],L[i-1]); for(int i=n;i>=1;i–)R[i]=max(R[i],R[i+1]); int ans=-inf; for(int i=1;i<=n;i++)ans=max(ans,L[i]+R[i+1]); return ans;}void Solve(){ scanf("%d",&n);int z=0,s=0,a=-inf,b=-inf; rep(i,n)scanf("%d",A+i+1),z+=A[i+1]>0,s+=A[i+1]; if(z<=2) { rep(i,n) { if(A[i+1]>b)b=A[i+1]; if(a<b)swap(a,b); } printf("%dn",a+b); return; } int ans=Cal(); rep(i,n)A[i+1]=-A[i+1]; ans=max(ans,s+Cal()); printf("%dn",ans);}int main(){ //freopen("in","r",stdin); int t;scanf("%d",&t); rep(i,t)Solve();}

17 thoughts on “网易有道资格赛1-最大和子序列

  1. 设L[x]表示1-x的最大子序列长度,R[x]表示x-n的最大子序列长度,答案很显然就是Max(L[x]+R[x+1])。。。然后如果跨越环了,那么它的对偶问题就是不选的那些肯定不跨越环,一样的DP可以算出来(为了方便把所有值取负就OK了。。)。。两个中的最大值就是答案了 ???? 楼主有没证明算法的正确性。按照理想情况可以求得最大和字串序列和记为A,剩余串中求出最大和字串序列和记为B,可以证明 A>=B>=0; 且AB串不存在重叠。但是最大结果并不等于A+B;而是假设A串中包含了最大负字串和为 -AF, 可以证明|AF|<=A;因此最大和子序列和为 MAX(A+B, A+|AF|);换句话说|AF|可能大于B

  2. …我是这样做的:先特判正数小于等于2个的情况。把串括成两倍,那么所有原串的字串在新的串中都有了,并且为所有长度为n的字串都是原串的一个循环。记下前缀和,然后对于一个i来说找到一个在max(0, i – n)到i – 1之间最小的一个前缀和,一减就是以i结尾的长度不超过n的最大子段和。然后把答案的区间记下来,把区间里面的数全部乘上-1,再做一次。。如果第二次小于0就不管,答案就是第一次的答案,否则把两次加起来就是答案。

  3. For treating CTS, adequate rest to the affected area 3 muscle factor x reviews to 4 months.
    Experience in sport will provide the fuel to be burned, and weight training does not provide the higher levels of TMAO than
    vegetarians after consuming L-carnitine. Seeing the doctor will give you that melt-in-your-mouth sensation you grew up on, and often traditional dishes have been lovingly prepared using the
    very versatile potato as the main” mass builders”. 71mg per 100g are also excellent sources of this protein
    will come from complex sources.

    Stop by my website: car shipping

  4. Good post. I learn something new and challenging on sites I stumbleupon everyday.
    It’s always exciting to read content from other authors
    and practice a little something from other web sites.

    My web page; virool Scam

  5. First off I would like to say superb blog! I had a quick
    question that I’d like to ask if you do not mind. I was curious
    to find out how you center yourself and clear your thoughts before writing.

    I’ve had a hard time clearing my thoughts in getting my ideas out.
    I truly do enjoy writing but it just seems like the first 10 to 15
    minutes are generally lost simply just trying to figure out how to begin.
    Any recommendations or tips? Thanks!

    my webpage … Mobil lån sms

  6. I was suggested this web site by my cousin. I’m not certain whether or not this post is written by way of him as no one else recognise such specific about my
    difficulty. You’re amazing! Thank you!

    My blog; hire movers weather by the hour minneapolis [Stacia]

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>