查看: 2876|回复: 9
收起左侧

找最大子矩阵 (哪家的我忘了)

|只看干货 |刷题
头像被屏蔽

分享帖子到朋友圈
wwwyhx | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:Google : Inplace rotate picture
下一篇:Microsoft : Find the largest square fits a rectangle
MontagueHu 2011-7-1 08:44:27 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (102)
 
 
0% (0)    👎
这个题naive的解法就是4*m*n,m和n是矩阵的dimension。

可以做一些result cache,另外构建一个矩阵t[m][n], t[i][j] = sum(a[0][0]+a[0][1]+a[1][0]+..a[i][j]),这也是o(m*n),但是常数项小了
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-7-1 09:07:09 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

MontagueHu 2011-7-3 01:33:36 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (102)
 
 
0% (0)    👎
题目不是二维矩阵,如果是m*n维度的,为什么不是整个矩阵的和最大?

anyway,思路大概是这样,given一个一维矩阵,找到[i...j],使得a[i]+...a[j]最大,这是o(n)的,参考programming perls。

扩展到2维矩阵是brute force,o(n3)
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-7-6 00:20:21 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

MontagueHu 2011-7-10 06:38:13 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (102)
 
 
0% (0)    👎
那就是o(n3),经典题是在一维子矩阵(有正有负)找出和最大的a[i]+...a[j],这个是O(n)
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-7-10 17:31:54 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

Imbalism 2011-10-19 10:02:09 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
M * M * N, from programming pearl
回复

使用道具 举报

smallacmer 2012-11-22 21:20:36 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
这一题的最大子矩阵和应该是
1  2 0 -3 4
-2 3 4 5 -1
1  1 5 3  0;23吧~
回复

使用道具 举报

johnwan 2012-12-4 15:46:23 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (21)
 
 
4% (1)    👎
wwwyhx 发表于 2011-7-10 17:31
思路是:
加入对于一个一维数组,可以在O(n)的时间复杂度内求出最大的sub array和.
这题的关键就是把一维数 ...

用一个一维数组记录就好了,careercup上的程序,非常tricky,我写了两遍,打算深深的记住它~
https://github.com/johnwan/maxSubMatrix/blob/master/.gitignore
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

>
快速回复 返回顶部 返回列表