p********7
发帖数: 549 | 1 求2维矩阵里面最大和的子矩阵的和。
-1 -2 3
3 2 -2
1 1 -1
最大和的是 7
没想到除了brute force还有什么办法 |
f***g
发帖数: 214 | 2 是不是Programming Pearl上的那道题？
O(n^2)? |
h**6
发帖数: 4160 | 3 我想到的方法是任选两行作为上下边，有O(n^2)种方法，对于每一种情况，进行一维最
大子数组处理，复杂度为O(n)。总复杂度为O(n^3)。
http://www.mitbbs.com/article_t/JobHunting/31671177.html
这贴中有人提到programming pearls 8.7.13，有书的朋友能不能简单介绍一下那是用
的什么方法？ |
s***r
发帖数: 1 | 4 最好应该只能O(n^3)吧
【在 p********7 的大作中提到】
: 求2维矩阵里面最大和的子矩阵的和。
: -1 -2 3
: 3 2 -2
: 1 1 -1
: 最大和的是 7
: 没想到除了brute force还有什么办法
|
f***g
发帖数: 214 | 5 嗯，O(n3),刚才说错了。
8.7.13的解答请看附件。
解法2就是预处理一下
每一行都等于当前列之前所有行的和。
每次就不用都加一遍了。
求第2行到第6行的和，就用第6行减去第2行
【在 h**6 的大作中提到】
: 我想到的方法是任选两行作为上下边，有O(n^2)种方法，对于每一种情况，进行一维最
: 大子数组处理，复杂度为O(n)。总复杂度为O(n^3)。
: http://www.mitbbs.com/article_t/JobHunting/31671177.html
: 这贴中有人提到programming pearls 8.7.13，有书的朋友能不能简单介绍一下那是用
: 的什么方法？
|
p********7
发帖数: 549 | 6 我觉得每行的最大max和矩阵的最大max没有关系的，有可能最大max的每一行都不是这
一行的
最大max array
【在 h**6 的大作中提到】
: 我想到的方法是任选两行作为上下边，有O(n^2)种方法，对于每一种情况，进行一维最
: 大子数组处理，复杂度为O(n)。总复杂度为O(n^3)。
: http://www.mitbbs.com/article_t/JobHunting/31671177.html
: 这贴中有人提到programming pearls 8.7.13，有书的朋友能不能简单介绍一下那是用
: 的什么方法？
|
p********7
发帖数: 549 | 7 you are right。
【在 f***g 的大作中提到】
: 嗯，O(n3),刚才说错了。
: 8.7.13的解答请看附件。
: 解法2就是预处理一下
: 每一行都等于当前列之前所有行的和。
: 每次就不用都加一遍了。
: 求第2行到第6行的和，就用第6行减去第2行
|
i**********e
发帖数: 1145 | 8 This is Maximum Sum of 2D array, an extension to maximum sum of 1D array.
See Kadane's algorithm:
http://en.wikipedia.org/wiki/Maximum_subarray_problem
The same problem is also in Online Judge. You can test your code there:
http://uva.onlinejudge.org/external/1/108.html
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
t*****j
发帖数: 1105 | 9 careerup上有道题类似的。
【在 p********7 的大作中提到】
: you are right。
|
K******g
发帖数: 1870 | 10 我的代码，复杂度O（m^2*n),根据programming pearls上的hints
int getMaxSubMatrix(int a[][], int m, int n)
{
int sum = 0;
int max = MIN_INTEGER;
int row_sum;
for(col_i=0; col_i
{
for(col_j=0; col_j<=col_i; col_j++)
{
for(row=0; row
{
row_sum = get_sum(row, col_i, col_j);
if(sum < 0) sum = row_sum;
else sum+= row_sum;
max = max
}
}
}
return max;
}
【在 p********7 的大作中提到】
: 求2维矩阵里面最大和的子矩阵的和。
: -1 -2 3
: 3 2 -2
: 1 1 -1
: 最大和的是 7
: 没想到除了brute force还有什么办法
|
A*********r
发帖数: 564 | 11 看了一下pearls， 觉得之前讨论的那个DP公式还是对的，跟pearls的预处理有同样的
效果。。
Define m(k,i,j) to be the maximum sum submatrix ending with the line A[k,i..
j]. （k is the row number, i, j is the left and right column number)
then the DP formula is m(k,i,j)=max{ 0, m(k-1,i,j)+sum{A[k,i..j]}}
注意到 m(k,1,j)其实就是第k行中从左到第j列的所有和，跟预处理的效果一样。。
你的这个例子，得到的 m(1, i,j) m(2, i,j), m(3, i, j)分别为：
（只考虑i<=j的情况）
0 0 0
0 1
3
3 5 3
2 1
1
4 7 4
4 1
0
最大和是7, m(3,1,2)也就是以第3行，第一列到第二列为最下面一条边的矩形。通过
backtrack应该可以找到前面的。。
【在 p********7 的大作中提到】
: 求2维矩阵里面最大和的子矩阵的和。
: -1 -2 3
: 3 2 -2
: 1 1 -1
: 最大和的是 7
: 没想到除了brute force还有什么办法
|
A*********r
发帖数: 564 | 12 再看了一下最里面的loop, 觉得dp的方法没有办法用在全是负数的矩阵里，这跟max subarray 在一维 O(n)那个办法有一样的局限性。。 |
