首页 > 代码库 > POJ 2479 Maximum sum
POJ 2479 Maximum sum
http://poj.org/problem?id=2479
题意：
给出一个整数串，求连续子串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 }
POJ 2479 Maximum sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。