HDU 1003 Max sum——分治法的应用,动态规划,前缀数组

原题: http://acm.hdu.edu.cn/showproblem.php?pid=1003

看到这题的时候一脸懵逼,网上寻找解答,发现都讲的不详细,变量声明也很短,根本看不出是什么用途,这里给出了我的解答,参考了网上各位大神的方法,加上了注释,方便学习。

##0x00 分治法解题

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>

struct Sequence
{
//表示一个数组

int sum;//数组元素之和
int leftPosition;//数组左边界位置
int rightPosition;//数组右边界位置
};

/*
求最大子列:

首先明确:
给定一个数列
其最大子列的范围,要么包括正中间的位置,要么全在最中间位置的左边,要么全在最中间位置的右边
这三种情况在迭代函数中分别处理
*/

struct Sequence getMaxSequence(int * sourceSequence, int leftPosition, int rightPosition) {

// printf("into: %d, %d\n",leftPosition,rightPosition);
int mediumPosition;

//范围:[leftPosition, rightPosition]
if (leftPosition == rightPosition) {
//给定范围内的子数列只有一个元素,构造一个struct sequence来描述;
struct Sequence sequence;
sequence.leftPosition = leftPosition;

sequence.rightPosition = rightPosition;
sequence.sum = sourceSequence[leftPosition];
// printf("return: %d, %d\n",sequence.leftPosition,sequence.rightPosition);

return sequence;
//将这个元素返回
}

//取得中间位置
mediumPosition = (leftPosition + rightPosition) / 2;

//构造三种struct来保存三种情况的返回值;
struct Sequence leftSequence;
struct Sequence rightSequence;
struct Sequence aroundSequence;

leftSequence = getMaxSequence(sourceSequence, leftPosition, mediumPosition);

rightSequence = getMaxSequence(sourceSequence, mediumPosition + 1, rightPosition);

//第三种情况下,先从中间向左边查找找出最大的和,再从中间向右边查找找出最大的和,相加得到横跨中间位置的最大值及范围
//先是左边
//先保存向左边出发遇到的第一个值
int leftMaxSumTmp = sourceSequence[mediumPosition];
//并保存该值的位置
aroundSequence.leftPosition = mediumPosition;

int leftSumTmp = 0;
for (int index = mediumPosition; index >= leftPosition; index--) {
leftSumTmp = leftSumTmp + sourceSequence[index];
if (leftSumTmp >= leftMaxSumTmp) {
//如果发现从中间到左边某一项的所有值之和比leftMaxSumTmp更大了,就更新leftMaxSumTmp
//并记录此位置到aroundSequence的leftPosition字段
leftMaxSumTmp = leftSumTmp;
aroundSequence.leftPosition = index;
}

}
//再是右边
//先保存向右边出发遇到的第一个值(因为到这里leftPosition和rightPosition不相等所以meiumPosition + 1(一定小于等于rightPosition)一定没有超过范围:[leftPosition, rightPosition]),不加if
int rightMaxSumTmp = sourceSequence[mediumPosition + 1];
//保存该值的位置
aroundSequence.rightPosition = mediumPosition + 1;

int rightSumTmp = 0;
for (int index = mediumPosition + 1; index <= rightPosition; index++) {
rightSumTmp = rightSumTmp + sourceSequence[index];
if (rightSumTmp >= rightMaxSumTmp) {
//如果发现从中间到右边某一项的所有值之和比rightMaxSumTmp更大了,就更新rightMaxSumTmp
//并记录此位置到aroundSequence的rightPosition字段
rightMaxSumTmp = rightSumTmp;
aroundSequence.rightPosition = index;
}

}

aroundSequence.sum = leftMaxSumTmp + rightMaxSumTmp;

//三选一返回,选sum最长的那个返回

// printf("return: %d, %d\n",finalSequence.leftPosition,finalSequence.rightPosition);
return (leftSequence.sum > rightSequence.sum) ? ((leftSequence.sum > aroundSequence.sum) ? leftSequence : aroundSequence) : ((rightSequence.sum > aroundSequence.sum) ? rightSequence : aroundSequence);

}
int main() {
int numOfCase , indexOfCase = 1,lengthOfSquence;
scanf("%d", &numOfCase);
while (indexOfCase <= numOfCase) {
scanf("%d",&lengthOfSquence);
int sourceSequence[100000];
for(int index = 0;index <lengthOfSquence;index++){
scanf("%d",sourceSequence + index);
}
struct Sequence aimSequence = getMaxSequence(sourceSequence,0,lengthOfSquence - 1);
printf("Case %d:\n%d %d %d\n", indexOfCase ,aimSequence.sum,aimSequence.leftPosition + 1,aimSequence.rightPosition + 1);
if(indexOfCase != numOfCase){
printf("\n");
}
indexOfCase++;
}

return 0;
}

寒假看到这样一篇文章,讲的很详细
http://conw.net/archives/9/#comment-25

##0x01 动态规划

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
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <cstring>

#define iinf 1e9

using namespace std;

// O(n)AC

// 动态规划
// 原先维护一个dp数组,dp[i]保存以第i个位子结尾的所有子列的最大和
// dp[i] = list[i] + max(dp[i - 1], 0);
// 自处省略这个数组,用两个变量来实现

int main(int argc, char const *argv[])
{

int T, N, last, now, ans, startpos, l, r;
scanf("%d", &T);
for (int j = 1; j <= T; j++) {
last = -1;
ans = -iinf;
l = 1;
r = 1;
scanf("%d", &N);

for (int i = 1; i <= N; i++) {
scanf("%d", &now);
if (last >= 0) {
last = now + last;

} else {
last = now;
startpos = i;

}

if (last > ans) {
ans = last;
l = startpos;
r = i;
}

}

if (j == 1) {
printf("Case 1:\n");
} else {
printf("\nCase %d:\n", j);
}

printf("%d %d %d\n", ans, l, r);

}

return 0;
}

##0x02 结合优化后的前缀数组

用这种用法的人似乎更多

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
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define iinf 1e9

using namespace std;

// O(n)AC

// 另一种结合前缀数组的方法
// data[i] = list[0...(i - 1)];
// data数组从1开始避免对边界的判断
// 则list[x...y] = data[y + 1] - data[x];
// i作为循环变量
// 维护data[i]的最小值mi,更新ans的最大值
// mi = min(mi, data[i])
// ans = max(data[i] - mi, ans)
// 可知若以第y个元素结尾的所有子列中list[x...y]为最优解,那么data[x]一定是data[1],data[2],data[3]...data[y](注意这里没有data[y+1],因为至少要有一个元素)中的最小值

int main(int argc, char const *argv[])
{

int T, N, sum, now, ans, min, minpos, l, r;
scanf("%d", &T);
for (int j = 1; j <= T; j++) {
sum = 0;
ans = -iinf;
min = 0;
minpos = 0;
l = 1;
r = 1;
scanf("%d", &N);

for (int i = 1; i <= N; i++) {
scanf("%d", &now);
sum += now;
if (sum - min > ans) {//更新答案,这里使用的是上一次循环的min值
r = i;
l = minpos + 1;
ans = sum - min;
}
if (sum < min) {//该判断语句不可和上一句调换,否则将可能出现最优解的数列长度为0;
min = sum;//更新本次循环的min,为在下一循环中使用到
minpos = i;
}
}

if (j == 1) {
printf("Case 1:\n");
} else {
printf("\nCase %d:\n", j);
}

printf("%d %d %d\n", ans, l, r);

}

return 0;
}