首页 > POJ解题报告 > POJ 2479 Maximum sum[DP]

POJ 2479 Maximum sum[DP]

类似于HDU 1003 Max Sum这一题,只不过这里是说把数组分为两段,把这两段的最大子段和求出来相加,求出最大的这样的值。
方法还是DP,跟HDU1003一样,从i = 0 to n – 1求一次最大子段和,然后从i = n – 1 to 0求一次最大子段和,最后相加判断即可。
POJ 2593 Maximum sum
传送:
POJ 2479 Maximum sum http://poj.org/problem?id=2479
POJ 2593 Max Sequence http://poj.org/problem?id=2593
POJ 2479的AC代码如下(2593稍微改一下即可):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
 
#define MAX_NUM (50000 + 10)
int num[MAX_NUM], l[MAX_NUM], r[MAX_NUM];
 
int main(int argc, char **argv)
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
 
	int n, m, i, res, tmp;
 
	scanf ("%d", &n);
	while (n--)
	{
		scanf ("%d", &m);
		tmp = 0;
		res = -10001;
		for (i = 0; i < m; ++i)
		{
			scanf ("%d", &num[i]);
			tmp += num[i];
			if (tmp > res)
				res = tmp;
			if (tmp < 0)
				tmp = 0;
			l[i] = res;
		}
		res = -10001;
		tmp = 0;
		for (i = m - 1; i >= 0; --i)
		{
			tmp += num[i];
			if (tmp > res)
				res = tmp;
			if (tmp < 0)
				tmp = 0;
			r[i] = res;
		}
		res = l[0] + r[1];
		for (i = 0; i < m - 1; ++i)
		{
			tmp = l[i] + r[i + 1];
			if (tmp > res)
				res = tmp;
		}
		printf ("%d\n", res);
	}
 
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> POJ 2479 Maximum sum[DP]
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 本文目前尚无任何评论.