Contents
Problem
上下、左右相連通，求矩形的元素最大和。(Maximum Sum Subarray)
(至少取一格)
Solution
作法可參考: http://www.csie.ntnu.edu.tw/~u91029/MaximumSubarray.html#4
方法一：
要讓左右相連，就把他從左到右複製一輪(可以不用複製完)。上下亦如是。
e.g.1
2
3
4
5
6
7
8
9
10
11
12
13原本的
1 2 3 4
5 6 7 8
9 A B C
修改後
1 2 3 4 | 1 2
5 6 7 8 | 5 6
9 A B C | 9 A
D E F G | D E
-------------
1 2 3 4 | 1 2
5 6 7 8 | 5 6
接著窮舉任意兩列(不得超過 n)，將它們之間同行的元素加在一起，合成一維的。{1+5+9+D,…}
最後就是利用 Kadane’s Algo. 算一維的最大區間，並隨時記錄最大值。
但要特別處理不能取超過原先矩陣的長度(也就是重複的)。
方法二：
可以再加速，為了不去處理取超過長度的問題，我們不複製左右，只複製到下方。
1 | 1 2 3 4 |
接著窮舉任意兩列的部分和方法一相同。
但我們還是要把左右相連給考慮進去。(e.g. C+9)
所以計算一維最大區間時，也去紀錄最小區間。
一維元素總和 - 最小區間和 = 左右相通的最大和(跨越中間)
最後再去比較 最大區間和 和 跨越中間 的值誰大即可。
Code
方法一：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
115
116
117
118
119
inline int get_num()
{
char c = getchar();
int n = 0;
bool flag = c == '-';
if (flag)
c = getchar();
while (c >= '0' && c <= '9')
{
n = n * 10 + c - '0';
c = getchar();
}
return flag ? -n : n;
}
int max1D(int arr[], int range, int limit)
{
int max = -1e9, sum = 0, now = 0;
for (int i = 0; i < range; i++)
{
//不能取重複的元素(超過 n 個)
if (now == limit)
{
int idx = i - now, local_max;
//先移掉最前面的
--now;
sum -= arr[idx];
//繼續移且記錄最大值(local_max)和其剩餘數量(now)
local_max = sum;
while (++idx < i)
{
sum -= arr[idx];
if (sum > local_max)
{
local_max = sum;
now = i - idx - 1;
}
}
sum = local_max;
}
if (sum > 0)
{
sum += arr[i];
now++;
}
else
{
sum = arr[i];
now = 1;
}
max = MAX(max, sum);
}
return max;
}
int main()
{
//freopen("test.out", "w", stdout);
int Case, board[N][N] = {}, sum[N] = {};
scanf("%d", &Case);
while (Case--)
{
int n, new_n;
scanf("%d ", &n);
new_n = (n << 1) - 2; //複製盤面後的大小 n + n - 2
/*
使它能取上下相連、左右相連的範圍。
複製從上到下、從左到右的範圍到對稱位置
*/
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
board[i][j] = board[i + n][j] = board[i][j + n] = board[i + n][j + n] = get_num();
if (n == 1)
{
printf("%d\n", board[0][0]);
continue;
}
/*for (int i = 0; i < new_n; i++)
{
for (int j = 0; j < new_n; j++)
printf("%3d ", board[i][j]);
putchar('\n');
}*/
//max2D
int max = -1e9;
for (int i = 0; i < n; i++)
{
for (int r = i; r < i + n && r < new_n; r++)
{
for (int k = 0; k < new_n; k++)
sum[k] += board[r][k];
max = MAX(max, max1D(sum, new_n, n));
}
memset(sum, 0, sizeof sum);
}
printf("%d\n", max);
}
return 0;
}
方法二：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
inline int get_num()
{
char c = getchar();
int n = 0;
bool flag = c == '-';
if (flag)
c = getchar();
while (c >= '0' && c <= '9')
{
n = n * 10 + c - '0';
c = getchar();
}
return flag ? -n : n;
}
int max1D(int arr[], int range)//Kadane's algo.
{
int max = -1e9, sum1 = 0; //找連續最大的
int min = 1e9, sum2 = 0; //找連續最小的，用來求循環最大的(跨越中間的)
int tot = 0;
for (int i = 0; i < range; i++)
{
tot += arr[i];
if (sum1 > 0)
sum1 += arr[i];
else
sum1 = arr[i];
max = MAX(max, sum1);
if (sum2 < 0)
sum2 += arr[i];
else
sum2 = arr[i];
min = MIN(min, sum2);
}
return MAX(max, tot - min); //(連續最大的, 跨越中間最大的)
}
int main()
{
//freopen("test.out", "w", stdout);
int Case, board[N * 2][N] = {}, sum[N] = {};
scanf("%d", &Case);
while (Case--)
{
int n, new_n;
scanf("%d ", &n);
new_n = (n << 1) - 2; //複製盤面後的大小 n + n - 2
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
board[i][j] = board[i + n][j] = get_num();//只對稱到下方(row)
if (n == 1)
{
printf("%d\n", board[0][0]);
continue;
}
//max2D
int max = -1e9;
//窮舉起始列
for (int i = 0; i < n; i++)
{
for (int r = i; r < i + n && r < new_n; r++) //逐次增加列數，最多取 n 個
{
//將 2D 合成 1D
for (int k = 0; k < n; k++)
sum[k] += board[r][k];
max = MAX(max, max1D(sum, n));
}
memset(sum, 0, sizeof sum);
}
printf("%d\n", max);
}
return 0;
}