Openjudge小练习--动态规划(1)--Maximum sum

 1 #include <cstdio>
 2 #include <algorithm>//max()函数
 3 using namespace std;
 4 int T, n, num[50050], r_max[50050], l_max[50050], ans;
 5 int main(){
 6     scanf("%d", &T);
 7     while(T--){
 8         scanf("%d", &n);
 9         //初始化
10         for(int i=0; i<n; ++i){
11             scanf("%d", &num[i]);
12             r_max[i] = l_max[i] = -10050;
13             ans = -20100;
14         }
15         //求以第i个数为结束的最大和子串
16         l_max[0] = num[0];
17         for(int i=1; i<n; ++i)
18             l_max[i] = max(l_max[i-1] + num[i], num[i]);
19         //求以第i个数为开始的最大和子串
20         r_max[n-1] = num[n-1];
21         for(int i=n-2; i>=0; --i)
22             r_max[i] = max(r_max[i+1] + num[i], num[i]);
23         //求以第i个数及之前的最大和子串
24         for(int i=1; i<n; ++i)
25             l_max[i] = max(l_max[i-1], l_max[i]);
26         //求以第i个数及之后的最大和子串
27         for(int i=n-2; i>=0; --i)
28             r_max[i] = max(r_max[i+1], r_max[i]);
29         //求以第i个数为分割的两个子串和最大和
30         for(int i=0; i<n-1; i++)
31             ans = max(ans, l_max[i] + r_max[i+1]);
32         printf("%d\n", ans);
33     }
34     return 0;
35 }