学步园

TAG 动态规划

设maxd[n]为前n个数的最大子序列和

maxd[n]=max{ maxd[n-1], sum[n]-minX } 其中，minX=min{sum[i] |   1<=i<n}

同理，设rmaxd[n]为从n到序列完的最大子序列和

则答案为max{ maxd[i]+rmaxd[i+1] },时间复杂度为O(n)

#include <stdio.h><br /> const int N=50000;<br /> int ans;<br /> int t,n;<br /> int a[N];<br /> int sum[N],rsum[N];<br /> int maxd[N],rmaxd[N];<br /> int minp;<br /> int max(int a, int b)<br /> {<br /> return a>b? a: b;<br /> }<br /> int min(int a,int b)<br /> {<br /> return a<b? a: b;<br /> }<br /> int main(int argc, char *argv[])<br /> {<br /> scanf("%d", &t);<br /> while ( t--)<br /> {<br /> scanf("%d", &n);<br /> for (int i=0; i<n; ++i)<br /> {<br /> scanf("%d", &a[i]);<br /> }<br /> sum[0]=a[0];<br /> rsum[n-1]=a[n-1];<br /> for (int i=1; i<n; ++i)<br /> {<br /> sum[i]=sum[i-1]+a[i];<br /> rsum[n-1-i]=rsum[n-i]+a[n-1-i];<br /> }<br /> maxd[0]=sum[0];<br /> minp=min(0,sum[0]);<br /> for (int i=1; i<n; ++i)<br /> {<br /> maxd[i]=max( maxd[i-1], sum[i]-minp );<br /> minp=min( minp, sum[i] );<br /> }<br /> rmaxd[n-1]=rsum[n-1];<br /> minp=min( 0,rsum[n-1] );<br /> for (int i=n-2; i>=0; --i)<br /> {<br /> rmaxd[i]=max( rmaxd[i+1], rsum[i]-minp);<br /> minp=min( minp, rsum[i] );<br /> }</p> <p> ans=sum[0]+rsum[1];<br /> for (int i=1; i<n-1; ++i )<br /> {<br /> ans=max( maxd[i]+rmaxd[i+1], ans);<br /> }</p> <p> printf("%d/n",ans );<br /> }<br /> return 0;<br /> }<br />