学步园

做两次dp.

对于数组dp[i]，表示下标从1到i的最大连续和。

#include<iostream><br /> #include<cstdio><br /> #include<cstring><br /> using namespace std;<br /> #define maxn 50005<br /> #define maxcost 9999999<br /> int dp[maxn],num[maxn];<br /> int main()<br /> {<br /> int t,i,n,max,sum;<br /> cin>>t;<br /> while(t--)<br /> {<br /> cin>>n;<br /> for(i=1;i<=n;i++)<br /> scanf("%d",&num[i]);<br /> sum=0;max=-maxcost;<br /> for(i=1;i<n;i++)<br /> {<br /> sum+=num[i];<br /> if(sum>max) max=sum;<br /> dp[i]=max;<br /> if(sum<0) sum=0;<br /> }<br /> max=-maxcost;sum=0;<br /> int ans=-maxcost;<br /> for(i=n;i>1;i--)<br /> {<br /> sum+=num[i];<br /> if(sum>max)max=sum;<br /> if(max+dp[i-1]>ans) ans=max+dp[i-1];<br /> if(sum<0) sum=0;<br /> }<br /> cout<<ans<<endl;<br /> }<br /> return 0;<br /> }