我个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();}
还有一种dp O(N)的吧 分2种情况:用 不用 用 不用 用 不用 用 不用 用 不用 分别12345 然后2次for.
回复Moun_ElemeNt:实际上是一样的。。
Orz…正解啊
设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
回复ljh_beer:没问题啊。。
…我是这样做的：先特判正数小于等于2个的情况。把串括成两倍，那么所有原串的字串在新的串中都有了，并且为所有长度为n的字串都是原串的一个循环。记下前缀和，然后对于一个i来说找到一个在max(0, i – n)到i – 1之间最小的一个前缀和，一减就是以i结尾的长度不超过n的最大子段和。然后把答案的区间记下来，把区间里面的数全部乘上-1，再做一次。。如果第二次小于0就不管，答案就是第一次的答案，否则把两次加起来就是答案。
学习了。不过你的代码有点风骚哦。。