这题怎么做？# JobHunting - 待字闺中
m*a
1 楼
N*N矩阵，矩阵的元素可正可负。请找出该矩阵的一个子矩阵（方块），使得其所有元
素之和在所有子矩阵中最大。
这个有O(N^3) 的DP解？网上搜出来的好像不对。
素之和在所有子矩阵中最大。
这个有O(N^3) 的DP解？网上搜出来的好像不对。
i*r
2 楼
O(n^3)的dp
1.枚举前后两行，O(n^2)
2.求最大子段和，O(n)
1.枚举前后两行，O(n^2)
2.求最大子段和，O(n)
m*a
3 楼
能展开讲讲吗？怎么枚举前后“两行”？
m*a
4 楼
能展开讲讲吗？怎么枚举前后“两行”？
i*r
5 楼
google搜“最大子矩阵和”
就知道了
就知道了
m*a
6 楼
Got it. thanks.
j*b
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);
}
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);
}
相关阅读
请问Firmware Test Engineer这个职位的面试内容google 面试题请问波士顿有没有什么大的IT公司啊？纯好奇问个sign on的问题求祝福有Amazon做PM的吗？面试归来, 求BLESS电话面试后一周了还没消息求教：这个程序为什么不能编译？H1b extension工作的问题请帮助！实习两个半月，开始接触到公司的核心的东西，是什么情况招工贴怎么被删了？新规定吗？大家一天花在找工作上的时间offer letter上面关于contract时间一般都是怎么写的？公司说和实习的mentor认识，问我可不可以拿到mentor的推荐信。。。G的recruiter要跟我在gchat上通话面试是fail掉一轮就全fail掉么？Amazon 物流管理软件开发老驴的故事OPT extension -- 这是什么情况？