w*e
2 楼
在它家以前订过也没啥问题啊，昨天晚上想订票，信用卡啥的都输入好了，订了，说我
选的票没有了。过半个钟头再查，说这票这价还有3张，又重新买，全折腾完，又说票
没了。今天换了个日子重新订，还是一样的，这不骗人玩呢吗？还有人也遇到这种情况
吗？
选的票没有了。过半个钟头再查，说这票这价还有3张，又重新买，全折腾完，又说票
没了。今天换了个日子重新订，还是一样的，这不骗人玩呢吗？还有人也遇到这种情况
吗？
d*d
3 楼
【 以下文字转载自 MusicPlayer 讨论区 】
发信人: desmond (葱油饼), 信区: MusicPlayer
标 题: 【仲夏语琴】电影音乐片段串烧
发信站: BBS 未名空间站 (Mon Jul 28 17:12:16 2014, 美东)
即兴弹了五六部喜爱的电影音乐片段，串在一起。大家可以听得出是哪些电影的主题音
乐吗？（说对了我发包子，每个ID限猜一个。）
https://app.box.com/s/gqzrqw842pgxbju4x8kg
发信人: desmond (葱油饼), 信区: MusicPlayer
标 题: 【仲夏语琴】电影音乐片段串烧
发信站: BBS 未名空间站 (Mon Jul 28 17:12:16 2014, 美东)
即兴弹了五六部喜爱的电影音乐片段，串在一起。大家可以听得出是哪些电影的主题音
乐吗？（说对了我发包子，每个ID限猜一个。）
https://app.box.com/s/gqzrqw842pgxbju4x8kg
w*l
4 楼
什么时候的题啊？今天问你的么？（解法改天上来....）
a*g
5 楼
不错啊
【在 d*****d 的大作中提到】
: 【 以下文字转载自 MusicPlayer 讨论区 】
: 发信人: desmond (葱油饼), 信区: MusicPlayer
: 标 题: 【仲夏语琴】电影音乐片段串烧
: 发信站: BBS 未名空间站 (Mon Jul 28 17:12:16 2014, 美东)
: 即兴弹了五六部喜爱的电影音乐片段，串在一起。大家可以听得出是哪些电影的主题音
: 乐吗？（说对了我发包子，每个ID限猜一个。）
: https://app.box.com/s/gqzrqw842pgxbju4x8kg
【在 d*****d 的大作中提到】
: 【 以下文字转载自 MusicPlayer 讨论区 】
: 发信人: desmond (葱油饼), 信区: MusicPlayer
: 标 题: 【仲夏语琴】电影音乐片段串烧
: 发信站: BBS 未名空间站 (Mon Jul 28 17:12:16 2014, 美东)
: 即兴弹了五六部喜爱的电影音乐片段，串在一起。大家可以听得出是哪些电影的主题音
: 乐吗？（说对了我发包子，每个ID限猜一个。）
: https://app.box.com/s/gqzrqw842pgxbju4x8kg
a*9
6 楼
divide and conqure?
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
d*d
7 楼
没办法，谷歌太强大了，上次在版上出的猜图题我自己截的图都一搜就有。音乐应该搜
不到吧。
【在 a*****g 的大作中提到】
: 不错啊
不到吧。
【在 a*****g 的大作中提到】
: 不错啊
t*i
8 楼
今天面的, 感觉挂了...
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
C*3
9 楼
倒数第二首是砂器把～
【在 d*****d 的大作中提到】
: 没办法，谷歌太强大了，上次在版上出的猜图题我自己截的图都一搜就有。音乐应该搜
: 不到吧。
【在 d*****d 的大作中提到】
: 没办法，谷歌太强大了，上次在版上出的猜图题我自己截的图都一搜就有。音乐应该搜
: 不到吧。
g*y
10 楼
comfort，遇到刁难你的了，这个题目属于面试题里面最高的难度级别
d*d
11 楼
没有啊，那个电影我都没看过。
【在 C***3 的大作中提到】
: 倒数第二首是砂器把～
【在 C***3 的大作中提到】
: 倒数第二首是砂器把～
a*9
12 楼
布个道吧 只能想到用分治，分4块再围着中间十字架找，大概是O(n^2),估计错的
【在 g*******y 的大作中提到】
: comfort，遇到刁难你的了，这个题目属于面试题里面最高的难度级别
【在 g*******y 的大作中提到】
: comfort，遇到刁难你的了，这个题目属于面试题里面最高的难度级别
y*n
13 楼
版主太有才！
拜
钢琴课+1
【在 d*****d 的大作中提到】
: 【 以下文字转载自 MusicPlayer 讨论区 】
: 发信人: desmond (葱油饼), 信区: MusicPlayer
: 标 题: 【仲夏语琴】电影音乐片段串烧
: 发信站: BBS 未名空间站 (Mon Jul 28 17:12:16 2014, 美东)
: 即兴弹了五六部喜爱的电影音乐片段，串在一起。大家可以听得出是哪些电影的主题音
: 乐吗？（说对了我发包子，每个ID限猜一个。）
: https://app.box.com/s/gqzrqw842pgxbju4x8kg
拜
钢琴课+1
【在 d*****d 的大作中提到】
: 【 以下文字转载自 MusicPlayer 讨论区 】
: 发信人: desmond (葱油饼), 信区: MusicPlayer
: 标 题: 【仲夏语琴】电影音乐片段串烧
: 发信站: BBS 未名空间站 (Mon Jul 28 17:12:16 2014, 美东)
: 即兴弹了五六部喜爱的电影音乐片段，串在一起。大家可以听得出是哪些电影的主题音
: 乐吗？（说对了我发包子，每个ID限猜一个。）
: https://app.box.com/s/gqzrqw842pgxbju4x8kg
I*s
14 楼
如果是正方形子矩阵, 答案见http://geeksforgeeks.org/?p=6257
属于DP, 时空复杂度都是O(n*n).
如果可以是长宽不等的子矩阵, 需要进一步考虑.
属于DP, 时空复杂度都是O(n*n).
如果可以是长宽不等的子矩阵, 需要进一步考虑.
d*d
15 楼
对！
【在 y****n 的大作中提到】
: 版主太有才！
: 拜
: 钢琴课+1
【在 y****n 的大作中提到】
: 版主太有才！
: 拜
: 钢琴课+1
i*e
16 楼
这题最优解可以O(n^2)。。。
要在面试时想出来的确有点难度。
以下两个链接有详细解法，欢迎大家踊跃讨论
http://www.drdobbs.com/184410529
http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module6/module6.html
要在面试时想出来的确有点难度。
以下两个链接有详细解法，欢迎大家踊跃讨论
http://www.drdobbs.com/184410529
http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module6/module6.html
C*3
17 楼
版主弹得也太老道乐，最后一首是上甘岭把～～
【在 d*****d 的大作中提到】
: 没有啊，那个电影我都没看过。
【在 d*****d 的大作中提到】
: 没有啊，那个电影我都没看过。
h*6
18 楼
我的解法是这样的，需要五个辅助矩阵: H, L, Lx, R, Rx, 大小都为n*m，与原矩阵X
相等。
H中记录当前点向上连续1的个数，或者称为当前最高一字柱的高度。
L中记录当前点向左连续1的个数。
Lx中记录当前最高一字柱向左最远延伸到的位置。
R中记录当前点向右连续1的个数。
Rx中记录当前最高一字柱向右最远延伸到的位置。
最后再遍历一遍，求出每个点对应当前最高一字柱向左右延拓的面积，最大值就是最大
矩形面积。
S = H(Rx-Lx+1)
优化方法：
第一次遍历可以求出H, L, Lx
第二次遍历可以求出R, Rx, S
每个矩阵只需要保留当前行和上一行，复杂度是O(2m)*5 = O(10m)
相等。
H中记录当前点向上连续1的个数，或者称为当前最高一字柱的高度。
L中记录当前点向左连续1的个数。
Lx中记录当前最高一字柱向左最远延伸到的位置。
R中记录当前点向右连续1的个数。
Rx中记录当前最高一字柱向右最远延伸到的位置。
最后再遍历一遍，求出每个点对应当前最高一字柱向左右延拓的面积，最大值就是最大
矩形面积。
S = H(Rx-Lx+1)
优化方法：
第一次遍历可以求出H, L, Lx
第二次遍历可以求出R, Rx, S
每个矩阵只需要保留当前行和上一行，复杂度是O(2m)*5 = O(10m)
d*d
19 楼
对，谢谢！
【在 C***3 的大作中提到】
: 版主弹得也太老道乐，最后一首是上甘岭把～～
【在 C***3 的大作中提到】
: 版主弹得也太老道乐，最后一首是上甘岭把～～
r*1
20 楼
挺好的。
【在 i**********e 的大作中提到】
: 这题最优解可以O(n^2)。。。
: 要在面试时想出来的确有点难度。
: 以下两个链接有详细解法，欢迎大家踊跃讨论
: http://www.drdobbs.com/184410529
: http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module6/module6.html
【在 i**********e 的大作中提到】
: 这题最优解可以O(n^2)。。。
: 要在面试时想出来的确有点难度。
: 以下两个链接有详细解法，欢迎大家踊跃讨论
: http://www.drdobbs.com/184410529
: http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module6/module6.html
C*3
21 楼
包子帖这么少回，狠少见哪。。原来觉得是砂器的那个应该是叶塞尼娅，找到电影听了
一下确定了。还有一个特别熟觉得是贝多芬传，看了一下别的板上的这帖原来是爱情故
事，不知道贝多芬传是不是也用了这首。。
【在 d*****d 的大作中提到】
: 没有啊，那个电影我都没看过。
一下确定了。还有一个特别熟觉得是贝多芬传，看了一下别的板上的这帖原来是爱情故
事，不知道贝多芬传是不是也用了这首。。
【在 d*****d 的大作中提到】
: 没有啊，那个电影我都没看过。
r*1
22 楼
不错啊。
【在 I**********s 的大作中提到】
: 如果是正方形子矩阵, 答案见http://geeksforgeeks.org/?p=6257
: 属于DP, 时空复杂度都是O(n*n).
: 如果可以是长宽不等的子矩阵, 需要进一步考虑.
【在 I**********s 的大作中提到】
: 如果是正方形子矩阵, 答案见http://geeksforgeeks.org/?p=6257
: 属于DP, 时空复杂度都是O(n*n).
: 如果可以是长宽不等的子矩阵, 需要进一步考虑.
y*n
23 楼
爱情故事么？
我一直以为是老版罗密欧和朱丽叶的主题音乐Love Theme
当然这曲子喜欢花样滑冰的同学都太熟悉了
这个还有梦之安魂曲的音乐做背景都用的很多
【在 C***3 的大作中提到】
: 包子帖这么少回，狠少见哪。。原来觉得是砂器的那个应该是叶塞尼娅，找到电影听了
: 一下确定了。还有一个特别熟觉得是贝多芬传，看了一下别的板上的这帖原来是爱情故
: 事，不知道贝多芬传是不是也用了这首。。
我一直以为是老版罗密欧和朱丽叶的主题音乐Love Theme
当然这曲子喜欢花样滑冰的同学都太熟悉了
这个还有梦之安魂曲的音乐做背景都用的很多
【在 C***3 的大作中提到】
: 包子帖这么少回，狠少见哪。。原来觉得是砂器的那个应该是叶塞尼娅，找到电影听了
: 一下确定了。还有一个特别熟觉得是贝多芬传，看了一下别的板上的这帖原来是爱情故
: 事，不知道贝多芬传是不是也用了这首。。
b*n
24 楼
辅助matrix A，原始matrix R
A[i][j]存 R[1][j]+...+R[i][j],即该column从0到i为止的和
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*********应为R[k][j]+...+R[i][j]，k-i是连续的1****
然后扫描每个row，row上的值实际构成一个histogram，求该histogram内最大的rectangle，O(N)
总体O（MN）
不知对不。。。
A[i][j]存 R[1][j]+...+R[i][j],即该column从0到i为止的和
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*********应为R[k][j]+...+R[i][j]，k-i是连续的1****
然后扫描每个row，row上的值实际构成一个histogram，求该histogram内最大的rectangle，O(N)
总体O（MN）
不知对不。。。
C*3
25 楼
我又去乐手之家看了一眼，爱情故事也不对，是照顾才给了个包子。罗与朱的音乐我就
不知道乐～
【在 y****n 的大作中提到】
: 爱情故事么？
: 我一直以为是老版罗密欧和朱丽叶的主题音乐Love Theme
: 当然这曲子喜欢花样滑冰的同学都太熟悉了
: 这个还有梦之安魂曲的音乐做背景都用的很多
不知道乐～
【在 y****n 的大作中提到】
: 爱情故事么？
: 我一直以为是老版罗密欧和朱丽叶的主题音乐Love Theme
: 当然这曲子喜欢花样滑冰的同学都太熟悉了
: 这个还有梦之安魂曲的音乐做背景都用的很多
l*k
26 楼
这个是不对的，R[1][j]+...+R[i][j]，加起来的和不代表连续的1啊，当中会有0。
rectangle
【在 b******n 的大作中提到】
: 辅助matrix A，原始matrix R
: A[i][j]存 R[1][j]+...+R[i][j],即该column从0到i为止的和
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: *********应为R[k][j]+...+R[i][j]，k-i是连续的1****
: 然后扫描每个row，row上的值实际构成一个histogram，求该histogram内最大的rectangle，O(N)
: 总体O（MN）
: 不知对不。。。
rectangle
【在 b******n 的大作中提到】
: 辅助matrix A，原始matrix R
: A[i][j]存 R[1][j]+...+R[i][j],即该column从0到i为止的和
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: *********应为R[k][j]+...+R[i][j]，k-i是连续的1****
: 然后扫描每个row，row上的值实际构成一个histogram，求该histogram内最大的rectangle，O(N)
: 总体O（MN）
: 不知对不。。。
y*n
27 楼
唔
看来版上对原声音乐的热情还有待提高:-)
再说一个吧
其实这个龟总如果听到一定很熟悉哈哈
千与千寻的The Name of Life
这段原声在久石让大叔的作品里，流传度恐怕与幽灵公主不相上下吧
【 在 desmond (葱油饼) 的大作中提到: 】
看来版上对原声音乐的热情还有待提高:-)
再说一个吧
其实这个龟总如果听到一定很熟悉哈哈
千与千寻的The Name of Life
这段原声在久石让大叔的作品里，流传度恐怕与幽灵公主不相上下吧
【 在 desmond (葱油饼) 的大作中提到: 】
b*n
28 楼
恩，改成R[k][j]+...+R[i][j]，k-i是连续的1
【在 l********k 的大作中提到】
: 这个是不对的，R[1][j]+...+R[i][j]，加起来的和不代表连续的1啊，当中会有0。
:
: rectangle
【在 l********k 的大作中提到】
: 这个是不对的，R[1][j]+...+R[i][j]，加起来的和不代表连续的1啊，当中会有0。
:
: rectangle
d*d
29 楼
也没什么，可能是我上传的地方不好，有些tx电脑打不开。叶塞尼亚答对了，那是个墨
西哥电影，虽然这部电影在中国比在墨西哥国内都有名多了。
【在 C***3 的大作中提到】
: 包子帖这么少回，狠少见哪。。原来觉得是砂器的那个应该是叶塞尼娅，找到电影听了
: 一下确定了。还有一个特别熟觉得是贝多芬传，看了一下别的板上的这帖原来是爱情故
: 事，不知道贝多芬传是不是也用了这首。。
西哥电影，虽然这部电影在中国比在墨西哥国内都有名多了。
【在 C***3 的大作中提到】
: 包子帖这么少回，狠少见哪。。原来觉得是砂器的那个应该是叶塞尼娅，找到电影听了
: 一下确定了。还有一个特别熟觉得是贝多芬传，看了一下别的板上的这帖原来是爱情故
: 事，不知道贝多芬传是不是也用了这首。。
c*p
30 楼
这个题是 largest rectangle under a histogram 的延伸。作为面试题是有点过分了。
【在 g*******y 的大作中提到】
: comfort，遇到刁难你的了，这个题目属于面试题里面最高的难度级别
【在 g*******y 的大作中提到】
: comfort，遇到刁难你的了，这个题目属于面试题里面最高的难度级别
j*l
31 楼
开始没看到，原来子矩阵是方的，这个难度降低了不少阿。
不过就是这样也不是一下子想到
0 1 1 0 1
1 1 0 1 0
0 1 0 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
方的话那个算法找到
1 1
1 1
不方的话应该是
1 1 1 1
1 1 1 1
那个算法无能为力
【在 I**********s 的大作中提到】
: 如果是正方形子矩阵, 答案见http://geeksforgeeks.org/?p=6257
: 属于DP, 时空复杂度都是O(n*n).
: 如果可以是长宽不等的子矩阵, 需要进一步考虑.
不过就是这样也不是一下子想到
0 1 1 0 1
1 1 0 1 0
0 1 0 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
方的话那个算法找到
1 1
1 1
不方的话应该是
1 1 1 1
1 1 1 1
那个算法无能为力
【在 I**********s 的大作中提到】
: 如果是正方形子矩阵, 答案见http://geeksforgeeks.org/?p=6257
: 属于DP, 时空复杂度都是O(n*n).
: 如果可以是长宽不等的子矩阵, 需要进一步考虑.
j*l
32 楼
就和哥德巴赫猜想或者费马大定理一样，题目描述很简单，可是找到解法很难
c*l
33 楼
makr
l*l
34 楼
能不能产生一个新的矩阵，然后矩阵的每个元素是数组。数组的第一个元素计算同一行
向左有多少个连续的1，第二个元素计算同一列向上有有多少个连续的1。
产生矩阵之后，每个数组取积。
非cs专业，所以瞎猜的，轻拍
向左有多少个连续的1，第二个元素计算同一列向上有有多少个连续的1。
产生矩阵之后，每个数组取积。
非cs专业，所以瞎猜的，轻拍
s*e
35 楼
Is my idea right? (Not CS major, welcome to make some comments)
Use a matrix A[i,j] to remember the size of all-1 matrix whose right-end
corner is (i,j) in the given matrix B.
if B[i,j]=0, A[i,j]=0
else
if A[i-1,j],A[i,j-1], A[i-1,j-1] are all >0
A[i,j]=A[i-1,j]+A[i,j-1]-A[i-1,j-1]+1
else
if A[i-1,j-1]==0 && (A[i-1,j]>0 || A[i,j-1]>0)
A[i,j]=max(A[i-1,j],A[i,j-1])+1
else
if A[i-1,j-1]==0 && A[i-1,j]=0 && A[i,j-1]=0
A[i,j]=1
else
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
Use a matrix A[i,j] to remember the size of all-1 matrix whose right-end
corner is (i,j) in the given matrix B.
if B[i,j]=0, A[i,j]=0
else
if A[i-1,j],A[i,j-1], A[i-1,j-1] are all >0
A[i,j]=A[i-1,j]+A[i,j-1]-A[i-1,j-1]+1
else
if A[i-1,j-1]==0 && (A[i-1,j]>0 || A[i,j-1]>0)
A[i,j]=max(A[i-1,j],A[i,j-1])+1
else
if A[i-1,j-1]==0 && A[i-1,j]=0 && A[i,j-1]=0
A[i,j]=1
else
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
s*e
36 楼
Found erros in my previous solution. It seems I should remember the sizes
for three directions: horizontal, vertical, and rectangular and then
establish the recursive relation. The above is not right.
【在 s*****e 的大作中提到】
: Is my idea right? (Not CS major, welcome to make some comments)
: Use a matrix A[i,j] to remember the size of all-1 matrix whose right-end
: corner is (i,j) in the given matrix B.
: if B[i,j]=0, A[i,j]=0
: else
: if A[i-1,j],A[i,j-1], A[i-1,j-1] are all >0
: A[i,j]=A[i-1,j]+A[i,j-1]-A[i-1,j-1]+1
: else
: if A[i-1,j-1]==0 && (A[i-1,j]>0 || A[i,j-1]>0)
: A[i,j]=max(A[i-1,j],A[i,j-1])+1
for three directions: horizontal, vertical, and rectangular and then
establish the recursive relation. The above is not right.
【在 s*****e 的大作中提到】
: Is my idea right? (Not CS major, welcome to make some comments)
: Use a matrix A[i,j] to remember the size of all-1 matrix whose right-end
: corner is (i,j) in the given matrix B.
: if B[i,j]=0, A[i,j]=0
: else
: if A[i-1,j],A[i,j-1], A[i-1,j-1] are all >0
: A[i,j]=A[i-1,j]+A[i,j-1]-A[i-1,j-1]+1
: else
: if A[i-1,j-1]==0 && (A[i-1,j]>0 || A[i,j-1]>0)
: A[i,j]=max(A[i-1,j],A[i,j-1])+1
p*7
37 楼
我觉得这个办法很好，histogram做一次O（N）每行都做O（M＊N）
【在 b******n 的大作中提到】
: 恩，改成R[k][j]+...+R[i][j]，k-i是连续的1
【在 b******n 的大作中提到】
: 恩，改成R[k][j]+...+R[i][j]，k-i是连续的1
y*n
38 楼
赞
【在 p********7 的大作中提到】
: 我觉得这个办法很好，histogram做一次O（N）每行都做O（M＊N）
【在 p********7 的大作中提到】
: 我觉得这个办法很好，histogram做一次O（N）每行都做O（M＊N）
s*a
39 楼
没有看那些网站，自己想出来的
用另外一个矩阵B表示原矩阵A，元素值B(i,j)是原矩阵位置到左上角子矩阵的1的数目。
那么判断A(i0,j0)->A(i1,j1) 是不是全一子矩阵就可以从 B(i1,j1)+B(i0,j0)-B(i1,
j0)-B(i0,j1)
得知 O(1)
From now on, we can do dynamic programming:
assume we found the maximum sub matrix for A(1,1) -> A(i,j),
we save the maximum submatrix which has the right-bottom corner at A(i,j_k),
and A(i_k,j), and maximum submatrix without limitation
go to A(i,j+1), A(i+1,j)
用另外一个矩阵B表示原矩阵A，元素值B(i,j)是原矩阵位置到左上角子矩阵的1的数目。
那么判断A(i0,j0)->A(i1,j1) 是不是全一子矩阵就可以从 B(i1,j1)+B(i0,j0)-B(i1,
j0)-B(i0,j1)
得知 O(1)
From now on, we can do dynamic programming:
assume we found the maximum sub matrix for A(1,1) -> A(i,j),
we save the maximum submatrix which has the right-bottom corner at A(i,j_k),
and A(i_k,j), and maximum submatrix without limitation
go to A(i,j+1), A(i+1,j)
p*7
40 楼
老题目了，就是用求histogram最大面积的方法做。
i*t
41 楼
面试给多长时间啊？
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
c*z
42 楼
方阵的话用Dynamic Programming
/**************************************************************
Maximum all-0 square submatrix problem -- Compiled under VC++ 2008.
Problem Description:
Given MxN binary matrix M, find the maximum all 0 square submatrix (
denoted by MASS) of it.
Example:
0000100
1100100
0000011 <= an answer is the 3x3 submatrix (row 2~4, col 0~2)
0000010
0000100
0010100
Algorithm Description:
The key idea is Dynamic Programming. Assume we are going
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
/**************************************************************
Maximum all-0 square submatrix problem -- Compiled under VC++ 2008.
Problem Description:
Given MxN binary matrix M, find the maximum all 0 square submatrix (
denoted by MASS) of it.
Example:
0000100
1100100
0000011 <= an answer is the 3x3 submatrix (row 2~4, col 0~2)
0000010
0000100
0010100
Algorithm Description:
The key idea is Dynamic Programming. Assume we are going
【在 t******i 的大作中提到】
: n*n 矩阵, 元素包括0 和1
: 求size(面积)最大的全1子矩阵.
: 想不出来,求教大家.
c*z
43 楼
我最后做出来了，也被默拒了。MSFT
不过是第二天做出来的。。。
总之就是再无消息。
不过是第二天做出来的。。。
总之就是再无消息。
c*z
44 楼
非方阵的我也做出来了，可是还是没有用。从此以后我就没有信心了。。。
/**************************************************************
Maximum All-0 Submatrix Problem (not necessarily square submatrix)
-- compiled under VC++ 2008
Problem Description:
Given MxN binary matrix R, find the maximum all 0 submatrix (not
necessarily square submatrix, denoted by MAS) of it.
Example:
0000100
1100100
0000011 <= an answer is the 2x5 submatrix (row 0~4, col 2~3)
1000010
0000100
001010
【在 I**********s 的大作中提到】
: 如果是正方形子矩阵, 答案见http://geeksforgeeks.org/?p=6257
: 属于DP, 时空复杂度都是O(n*n).
: 如果可以是长宽不等的子矩阵, 需要进一步考虑.
相关阅读
不打算去看contagion的進來看劇透问个电影有没有哪个电影你认为价值观是严重错误的?kites求鉴定一个人我的身体是属于国家和人民的。 (转载)壁画，还是画壁，简直无里头至极Re: 有必要把家庭矛盾闹上网吗？ (转载)看了８０年代的偶像片 庐山恋Cloud Atlas (2012 Movie) (转载)Moneyball是部蛮有意思的电影这两天被Tom Cruise演的吸血鬼迷住了 (转载)sifi里关于机器人的好片子塔木中秋晚会 DV短剧：爱情公寓外传[欧美][命运规划局][马特达蒙@愛蜜莉布朗](FSC@1080p-BRRip)武侠 观后感黑色幽默老电影<骗中骗>the sting太欢乐了非主流电影名查询Ben Foster和Ryan Gosling这么像啊！发现一部好片子,