本题是一道稍显困难的动态规划问题，需要仔细观察题目内容，转化为已经解答过的题目。
假设有一个二维 n * n 的矩阵，矩阵的内容为不同的整数。对它的任意子矩阵的所有元素的求和，这些和中最大的数是多少？
输入有两部分，第一部分为 n 的大小，不会超过100。第二部分为 n * n 个整数，为矩阵中的各个元素。
示例输入为：
1
2
3
4
5
| 4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2
|
输出最大子矩阵元素和。
对应的示例输出为：
本题是动态规划经典问题“最大字段和”的变体。要求解这个问题就要很熟悉“最大字段和”问题和它的解法。
最大字段和问题可以简单的解释为下面的例题：
对于任意整数随意排列组成的一维数组，设它的子数组为数组中的任意连续元素（元素数不为 0）组成，在它的可能组成的所有子数组中，所有元素和最大为多少？
这个例题的解法很简单：
对于 n 个元素的数组 a 每个元素为 a1,a2 … an，构造元素个数也为 n 的辅助数组 s，且有对于第 i 个元素有 s[i] = s[i-1] > 0 ? s[i - 1]+ a[i] : a[i]，同时 s[0] = a[0]。这样数组 s 中的最大元素就是所要求的答案。用 Java 代码表示为：
1
2
3
4
5
6
7
8
9
10
| int maxSum(int a[]) {
int max = Integer.MIN_VALUE;
int temp = 0;
for (int num : a) {
if (temp > 0) temp += num;
else temp = num;
if (temp > max) max = temp;
}
return max;
}
|
这样，就不用真的对所有可能的子数组进行求和，然后再比较和的大小。
本题看似是二维数组存储的结果，无法应用已有的知识进行解答。但是，实际上因为题目的要求是比较子矩阵所有元素的和，那么可以将二维数组压缩构造为一维数组，转化为最大字段和问题。
压缩思想如下：
假设 n * n 的数组 a 中，和最大的子数组左上角元素坐标为 (r,i)，右下角坐标为 (k,j) ，示意图如下所示：
1
2
3
4
5
6
7
8
9
10
| | a11 …… a1i …… a1j …… a1n |
| a21 …… a2i …… a2j …… a2n |
| . . . . . . . |
| . . . . . . . |
| ar1 …… ari …… arj …… arn |
| . . . . . . . |
| . . . . . . . |
| ak1 …… aki …… akj …… akn |
| . . . . . . . |
| an1 …… ani …… anj …… ann |
|
这个子数组当然被第 r 行 和第 k 行包裹，把这两行之间（包含它们两行）提取出来，就是：
1
2
3
4
| | ar1 …… ari …… arj …… arn |
| . . . . . . . |
| . . . . . . . |
| ak1 …… aki …… akj …… akn |
|
原题目的解也必定是这个数组的子数组元素和最大值，而且对子数组的元素求和可以分解为两个步骤：先求子数组的各列的元素和，然后再相加求整体元素和。
这样，不妨纵向压缩这个数组得到一维数组：
1
| | s1 …… si …… sj …… sn |
|
一维数组每个元素都是上面的二维数组的各个列的元素和，这样原有的二维数组子数组求和问题就转换成了一维数组字段求和问题。
最后，整个问题就变成了从第一行开始，取出任意两行数组，对于它们之间的元素（包含这两行元素）求子数组元素和最大值。即转换出多个最大字段和问题，然后求出它们各自的解的最大值即可。
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
| import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[][] buf = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
buf[i][j] = in.nextInt();
}
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int temp = 0;
for (int k = 0; k < n; k++) {
buf[i][k] += buf[j][k];
if (temp > 0) {
temp += buf[i][k];
} else {
temp = buf[i][k];
}
if (temp > max) max = temp;
}
}
}
System.out.println(max);
}
}
|