問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2479http://acm.pku.edu.cn/JudgeOnline/problem?id=2593http://acm.pku.edu.cn/JudgeOnline/problem?id=1050思路:
基礎(chǔ): 最大子段和問(wèn)題
給定N個(gè)整數(shù)(可能為負(fù))組成的序列a1, a2, a3, ..., aN，求子段ai, a(i+1), ... , aj的和的最大值
非常典型的動(dòng)態(tài)規(guī)劃，狀態(tài)遷移方程:
f(i) = max(ai, f[i-1]+ai), f(i)表示以ai結(jié)尾的最大子段和據(jù)此我們可以得到O(n)的求解算法
PKU 2479與2593這兩題其實(shí)是同一個(gè)問(wèn)題(
買(mǎi)一送一)，都是上述最大子段和問(wèn)題的變形
一樣非常自然的想法是枚舉所有可能的"分開(kāi)點(diǎn)", 然后分別計(jì)算前后兩個(gè)子數(shù)組的最大子段和，不過(guò)如果依次枚舉的話是會(huì)超時(shí)的
這時(shí)候就需要利用對(duì)于上述f(i)表達(dá)式的理解了, 我們可以依次從頭到尾、從尾到頭掃描兩次原數(shù)組，并把相應(yīng)的最大子段和分別保存起來(lái)，稱為hd[i]和tl[i], 這里注意f(i)并非是最大子段和
假設(shè)現(xiàn)在枚舉到分開(kāi)點(diǎn)t, 那么a[0..t]的最大子段和可以通過(guò)hd[i]獲得，a[t+1...len]的最大子段和則可以通過(guò)tl[i]獲得
1 /*
2 * hd[i] stores the maximum sub-segment from arr[0..i]
3 * tl[i] stores the maximum sub_segment from arr[i+1..n-1]
4 */
5 long *hd, *tl;
6
7 long
8 max_subsum(int *arr, long N)
9 {
10 long i, temp, max;
11 /* hd */
12 hd[0] = max = arr[0];
13 for(i=1; i<N; i++) {
14 temp = hd[i-1] + arr[i];
15 hd[i] = temp>arr[i] ? temp : arr[i];
16 }
17 for(i=1; i<N; i++) {
18 hd[i] = hd[i] > max ? hd[i] : max;
19 max = hd[i];
20 }
21 /* tl */
22 tl[N-1] = max = arr[N-1];
23 for(i=N-2; i>=0; i--) {
24 temp = tl[i+1] + arr[i];
25 tl[i] = temp>arr[i] ? temp : arr[i];
26 }
27 for(i=N-2; i>=0; i--) {
28 tl[i] = tl[i] > max ? tl[i] : max;
29 max = tl[i];
30 }
31 }
32
33 long
34 enumerate()
35 {
36 long i, temp, max = hd[0] + tl[1];
37 for(i=1; i<n-1; i++) {
38 temp = hd[i] + tl[i+1];
39 max = max>temp ? max : temp;
40 }
41 return max;
42 }
PKU 1050是一道"隱藏"地比較深的最大子段和問(wèn)題，之所以說(shuō)它隱藏的比較深，是因?yàn)轭}目要求的是求最大子矩陣問(wèn)題
上網(wǎng)搜了別人的思路，才發(fā)現(xiàn)這題是可以轉(zhuǎn)化成求最大子段和問(wèn)題的：只要將矩陣的行或者列合并即可
不得不感嘆這思路的精妙啊呵呵
1 int
2 max_subsum(int *arr, int N)
3 {
4 int i, t, max;
5 max = t = arr[0];
6 for(i=1; i<N; i++) {
7 t = t+arr[i]>arr[i] ? t+arr[i] : arr[i];
8 max = max>t ? max : t;
9 }
10 return max;
11 }
12
13 int
14 enumerate()
15 {
16 int t, max = 0;
17 int i, j, k, len, temp[col];
18 memset(temp, 0, sizeof(int)*col);
19 for(len=1; len<=row; len++) {
20 for(i=0; i<row; i++) {
21 for(j=i; j<len; j++) {
22 for(k=0; k<col; k++) {
23 temp[k] += arr[j][k];
24 }
25 }
26 t = max_subsum(temp, col);
27 max = max>t ? max : t;
28 memset(temp, 0, sizeof(int)*col);
29 }
30 }
31 return max;
32 }