这题怎么做？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

这题怎么做？

这题怎么做？# JobHunting - 待字闺中

m*a2012-02-17 08:02

1 楼

N*N矩阵，矩阵的元素可正可负。请找出该矩阵的一个子矩阵（方块），使得其所有元
素之和在所有子矩阵中最大。
这个有O(N^3) 的DP解？网上搜出来的好像不对。

i*r2012-02-17 08:02

2 楼

O(n^3)的dp
1.枚举前后两行，O(n^2)
2.求最大子段和，O(n)

m*a2012-02-17 08:02

3 楼

能展开讲讲吗？怎么枚举前后“两行”？

m*a2012-02-17 08:02

4 楼

能展开讲讲吗？怎么枚举前后“两行”？

i*r2012-02-17 08:02

5 楼

google搜“最大子矩阵和”
就知道了

m*a2012-02-17 08:02

6 楼

Got it. thanks.

j*b2012-02-17 08:02

7 楼

public static void main(String[] args) {
int[][] matrix = { { -1, -2, -3 }, { 4, 5, -6 }, { -7, -8, -9 } };
int n = 3;
int sum[][][] = new int[n][n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
sum[i][j][j] = matrix[i][j];
}
for (int j = 1; j < n; j++) {
for (int k = 0; k < n - j; k++) {
//dp
sum[i][k][k + j] = sum[i][k][k] + sum[i][k + 1][k + j];
}
}
}
Integer Max = null;
// find the biggest
int a1 = 0, a2 = 0, b1 = 0, b2 = 0;
for (int b = 0; b < n; b++) {
for (int c = b; c < n; c++) {
int s = 0;
Integer max = null;
int maxs = 0, maxe = 0;
int start = 0;
for (int a = 0; a < n; a++) {
s += sum[a][b][c];
if (max == null || s > max) {
max = s;
maxs = start;
maxe = a;
}
if (s <= 0) {
start = a + 1;
s = 0;
}
}
if (Max == null || max > Max ) {
Max = max;
a1 = maxs;
a2 = maxe;
b1 = b;
b2 = c;
}
}
}
System.out.println("row " + a1 + "-" + a2);
System.out.println("col " + b1 + "-" + b2);
System.out.println("sum " + Max);
}