f**********t
发帖数: 1001 | 1 我有一个M*N维的矩阵
希望找到一个m*n维的子矩阵使得其元素和最大
这个子矩阵的行和列不一定要连续
这个问题有好的解么？
就比如说，一个矩阵是3*3的
设每行每列的编号是(1, 1,) (1, 2), (1, 3)(2, 1,) (2, 2), (2, 3)(3, 1,) (3, 2)
, (3, 3)，则(1, 1)(1, 3)(3, 1)(3, 3)这四个点组成的也算是个子矩阵
目前有想法，但时间复杂度很大。感觉好像只有枚举法来做这个问题。不知大家有没有
更好的解法。 | i******r
发帖数: 793 | 2 经典算法题
可以枚举左上和右下两个顶点，复杂度O(n^4)
模仿最大子段和的O(n)算法，可以优化到O(n^3)
请自行google ‘最大子矩阵’ | k****e
发帖数: 116 | 3 他的题目行和列都可以不连续的，你说的貌似不大行
【在 i******r 的大作中提到】
: 经典算法题
: 可以枚举左上和右下两个顶点，复杂度O(n^4)
: 模仿最大子段和的O(n)算法，可以优化到O(n^3)
: 请自行google ‘最大子矩阵’
| i******r
发帖数: 793 | 4 晕，看错了。。。
我不太理解不连续是啥意思
按照我的理解，把矩阵扫描一遍，找到所有的大于0的数，然后找个矩阵能包括所有正
数就行。
如果没有大于0的数，就找个最大的负数就行了。
【在 k****e 的大作中提到】
: 他的题目行和列都可以不连续的，你说的貌似不大行
| k****e
发帖数: 116 | 5 这个问题的size本身是exponential的，2^(2n), 我是想不出什么好办法
【在 i******r 的大作中提到】
: 晕，看错了。。。
: 我不太理解不连续是啥意思
: 按照我的理解，把矩阵扫描一遍，找到所有的大于0的数，然后找个矩阵能包括所有正
: 数就行。
: 如果没有大于0的数，就找个最大的负数就行了。
| y****n
发帖数: 743 | 6 我的想法是:
1. 建立矩阵1，纵向用slide window对原矩阵求和。
2. 建立矩阵2，横向用slide window对矩阵1求和。
3. 扫描矩阵2，找到最大值就是目标矩阵所在位置
复杂度O(M*N)，不知道有没有遗漏什么 | b******7
发帖数: 92 | 7 这个case就过不了
1 2 -3
3 4 1
【在 y****n 的大作中提到】
: 我的想法是:
: 1. 建立矩阵1，纵向用slide window对原矩阵求和。
: 2. 建立矩阵2，横向用slide window对矩阵1求和。
: 3. 扫描矩阵2，找到最大值就是目标矩阵所在位置
: 复杂度O(M*N)，不知道有没有遗漏什么
|
|
