学步园

//动态规划<br /> //dp1[i]数组表示从左往右以i为终点最大连续和<br /> //dp2[i]数组表示从右往左以i为终点最大连续和<br /> //dp3[i]数组表示从右往左记录下到当前位置能取到的最大值，即记忆化，使调用该值不必再次循环<br /> //最终最大值_max = max(dp1[i] + dp3[i+1])<br /> //arr: 1,-1,2,2,3,-3,4,-4,5,-5<br /> //dp[1]: 1, 0,2,4,7, 4,8, 4,9, 4<br /> //dp[2]: 9, 8,9,7,5, 2,5, 1,5,-5<br /> //dp[3]: 9, 9,9,7,5, 5,5, 5,5,-5<br /> //MAX : 10,9,9,9,12,9,13,9,-4 X 故答案为13<br /> //注意考虑全为负数的情况！<br /> //scanf 比 cin快很多，此题用cin一定TLE!<br /> #include<cstdio><br /> #include<iostream><br /> #define INF -2147483647;<br /> using namespace std;<br /> int arr[50001],dp1[50001],dp2[50001],dp3[50001];<br /> int test,n,_max;<br /> int main()<br /> {<br /> dp1[0] = 0;<br /> scanf("%d",&test);<br /> while(test--)<br /> {<br /> _max = INF;<br /> scanf("%d",&n);<br /> dp2[n+1] = 0;<br /> for(int i = 1;i <= n;++i)<br /> {<br /> scanf("%d",&arr[i]);<br /> dp1[i] = max(dp1[i-1] + arr[i],arr[i]);<br /> }<br /> int temp = INF;<br /> for(int i = n;i > 1;--i)<br /> {<br /> dp2[i] = max(dp2[i+1] + arr[i],arr[i]);<br /> if(dp2[i] > temp)<br /> {<br /> temp = dp2[i];<br /> dp3[i] = dp2[i];<br /> }<br /> else<br /> dp3[i] = temp;<br /> if(dp3[i] + dp1[i-1] > _max)<br /> _max = dp3[i] + dp1[i-1];<br /> }<br /> printf("%d/n",_max);<br /> }<br /> return 0;<br /> }