经典dpdp 求最大片段和的子序列

缘起

这是一道非常古老的面试题了. 所幸 hdu上有此题的提交. Max Sum

分析

题意很裸

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
给一个数组a[1,...,n], 你的任务是找出和最大的子序列, 例如 6,-1,5,4,-7, 最大子序列是 6 + (-1) + 5 + 4 = 14. 

【输入】
第一行是样例数 T(1<=T<=20). 然后下面是T行数据, 每一行第一个数字是数组的元素个数n(1<=n<=100000)，后
面紧跟着是n个数字.所有的数字保证在 [-1000,1000]范围内.

【输出】
对每个样例，你要输出两行，第一行是 "Case #:", #用第几个样例代替. 第二行包含三个数字，第一个数字是最大
和, 第二个数字是这个片段的其实索引. 第三个数字是这个片段的终结索引. 如果答案不止一个的话, 输出第一个.
两个样例之间用一个空行隔开.

【样例输入】
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

【样例输出】
Case 1:
14 1 4

Case 2:
7 1 6

用dp.令 dp[i]表示以 a[i] 为结尾的最大片段和（注意，如果令dp[i]为a[1,..,i]中最大片段和的话, 则递推公式就显得复杂了, 所以dp问题中, 选择合理的dp对象是很重要的）. 则显然有

1
2
dp[i] =  a[i]+max(dp[i-1],0),    1<i<=n
dp[1] = a[1]

程序如下

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
//#include "stdafx.h"
#include <stdio.h>
//#define LOCAL

const int MAX_N = 100005;

int a[MAX_N], n;

void dp()
{
	int _max = a[1], _max_start=1, _max_end =1, x = a[1], y = 1, z = 1; // _max是最大片段和, _max_start是起始索引, _max_end是片段的终结索引, x,y,z 是以a[i]为结尾的最大和片段的和、起始索引、终结索引
	for (int i = 2; i<=n; i++)
	{
		x<0?x = a[y=z=i]: x += a[z=i]; // 注意, 要是 <0, 这样即便dp[i-1]为0, 也要和a[i]并在一起, 这样的话, 就能找到最早出现的那个了
		if (_max<x) _max = x,_max_start = y,_max_end = z;
	}
	printf("%d %d %d\n", _max, _max_start, _max_end);
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif

	int t;
	scanf("%d", &t);
	int cse = 0;
	while(t--)
	{
		if (cse++) puts("");
		scanf("%d", &n);
		for (int i = 1;i<=n;i++) scanf("%d", a+i);
		printf("Case %d:\n", cse);
		dp();
	}
	return 0;
}

ac情况如下

Status Accepted
Time 31ms
Memory 2104kB
Length 903
Lang C++
Submitted 2019-07-20 13:28:14
Shared
RemoteRunId 29787526