这题怎么做？# 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);
}
相关阅读
G家选组求推荐请教一个用competing offer跟G家抬价的问题求netflix内推刷题对于有工作经验的, 基本没用找工作 onsite interview以后继续onsite 做题？弱问：不好意思，这个CODE问题在哪里？我就不信就我一个人在等待大学工作的录取面试之后recruiter的邮件大家觉得Niantic这个公司估值可能能有多少？请问amazon这个会是technical phone interview吗？HERE工作十年体会 – 续篇三有孩子有工作的刷题真是痛苦中部一个startup，薪水是不是太低？Walmar is hiring Principal Software Engineerairbnb大事不妙了求帮忙内推Apple Supply chain职位snapchat这家公司大家看好吗？How to answer this application question?有人sue google for age discrimination了真的应该老中帮老中吗？