POJ 2479 Maximum sum (DP&双最大子段和)

发布时间:2016-12-9 8:22:47 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ 2479 Maximum sum (DP&双最大子段和)",主要涉及到POJ 2479 Maximum sum (DP&双最大子段和)方面的内容,对于POJ 2479 Maximum sum (DP&双最大子段和)感兴趣的同学可以参考一下。

Maximum sum http://poj.org/problem?id=2479 Time Limit: 1000MS Memory Limit: 65536K Description Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below: Your task is to calculate d(A). Input The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input.  Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case. Output Print exactly one line for each test case. The line should contain the integer d(A). Sample Input 1 10 1 -1 2 2 3 -3 4 -4 5 -5 Sample Output 13 Hint In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.  Huge input,scanf is recommended. 首先,由于要求左右两段,必须把左边最大子段和的右端点从1~n遍历下,求每个值对应的最大子段和;右边从n~1遍历。 每部分最大子段和由转移方程left[i] = max(left[i - 1] + v[i], v[i])给出。 最后,求left[i - 1] + right[i]的最大值。(充分利用左右两部分的范围) 完整代码: /*422ms,704KB*/ #include <cstdio> #include <algorithm> using namespace std; int v[50001], left[50001], right[50001]; int main(void) { int icase; scanf("%d", &icase); while (icase--) { int size; scanf("%d", &size); for (int i = 0; i < size; ++i) scanf("%d", &v[i]); left[0] = v[0]; for (int i = 1; i < size; ++i) left[i] = max(left[i - 1] + v[i], v[i]); for (int i = 1; i < size; ++i) left[i] = max(left[i], left[i - 1]); right[size - 1] = v[size - 1]; for (int i = size - 2; i >= 0; --i) right[i] = max(right[i + 1] + v[i], v[i]); for (int i = size - 2; i >= 0; i--) right[i] = max(right[i], right[i + 1]); int res = left[0] + right[1]; for (int i = 2; i < size; ++i) res = max(res, left[i - 1] + right[i]); printf("%d\n", res); } return 0; }

上一篇:jar打包 jar line too long 异常处理方法
下一篇:GridView的RowCommand里取列的值

相关文章

相关评论