poj1741，POJ 2479 Maximum sum

2023-11-19 阅读 23 评论 0

摘要：http://poj.org/problem?id=2479 題意： poj1741。給出一個整數串，求連續子串1和連續子串2，不相交并且串1加串2的和最大。 ? 思路：其實就是求最大連續和，題意要求就是求兩段最大連續和。我們可以從左邊和右邊分別求最大連續和，

http://poj.org/problem?id=2479

題意：

poj1741。給出一個整數串，求連續子串1和連續子串2，不相交并且串1加串2的和最大。

思路：

其實就是求最大連續和，題意要求就是求兩段最大連續和。我們可以從左邊和右邊分別求最大連續和，代碼中的dp_l[i]就是1~i的最大連續和，dp_r[i]則是i~n的最大連續和。

 1 #include<iostream> 
 2 #include<string>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 50000 + 5;
 8 const int INF = -10000000;
 9 
10 int n;
11 int a[maxn];
12 int l[maxn], r[maxn];
13 int dp_l[maxn], dp_r[maxn];
14 
15 int main()
16 {
17     //freopen("D:\\txt.txt", "r", stdin);
18     int T;
19     scanf("%d", &T);
20     while (T--)
21     {
22         scanf("%d", &n);
23         for (int i = 1; i <= n; i++)
24             scanf("%d", &a[i]);
25         l[0] = dp_l[0] = INF;
26         r[n+1] = dp_r[n+1]=  INF;
27         for (int i = 1; i <= n; i++)
28         {
29             l[i] = max(l[i - 1] + a[i], a[i]);
30             dp_l[i] = max(dp_l[i - 1], l[i]);
31         }
32         for (int i = n; i >= 1; i--)
33         {
34             r[i] = max(r[i + 1] + a[i], a[i]);
35             dp_r[i] = max(dp_r[i + 1], r[i]);
36         }
37         int ans = INF;
38         for (int i = 1; i <= n; i++)
39         {
40             ans = max(dp_l[i] + dp_r[i + 1], ans);
41         }
42         printf("%d\n", ans);
43     }
44     return 0;
45 }