Maximal Rectangle如果不要求是Rectangle就要简单得多# JobHunting - 待字闺中
a*e
1 楼
抱怨一下，开始按算面积的想，后来发现题没理解对。有人面试碰到这种题吗？感觉不
像DP
像DP
k*p
2 楼
如果是square就可以DP
b*i
3 楼
请问你指的是这个吗？
http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1
1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]
1-b)看不懂啊，为什么是这三个里面最小的？
【在 k****p 的大作中提到】
: 如果是square就可以DP
http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1
1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]
1-b)看不懂啊，为什么是这三个里面最小的？
【在 k****p 的大作中提到】
: 如果是square就可以DP
b*i
4 楼
哦，画了个图，想通了。
【在 b******i 的大作中提到】
: 请问你指的是这个吗？
: http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1
: 1) Construct a sum matrix S[R][C] for the given M[R][C].
: a) Copy first row and first columns as it is from M[][] to S[][]
: b) For other entries, use following expressions to construct S[][]
: If M[i][j] is 1 then
: S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
: Else /*If M[i][j] is 0*/
: S[i][j] = 0
: 2) Find the maximum entry in S[R][C]
【在 b******i 的大作中提到】
: 请问你指的是这个吗？
: http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1
: 1) Construct a sum matrix S[R][C] for the given M[R][C].
: a) Copy first row and first columns as it is from M[][] to S[][]
: b) For other entries, use following expressions to construct S[][]
: If M[i][j] is 1 then
: S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
: Else /*If M[i][j] is 0*/
: S[i][j] = 0
: 2) Find the maximum entry in S[R][C]
相关阅读
请教面试细节!OPT 加急经验大家电面一般是在哪进行？Google 客服面试过程-一次失败的经历看实习后3万的贴子也有感H1B 申了一个月没消息，正常么？h1-b申请了1个星期了，还是acceptance状态。。投简历投的都麻木了，一个一个的SEND。最后都不知道自己投的是什么了做oracle的数据库如何？问一个stl:: set的问题报offers给挂身份的学校交学费刚电面完，求安慰。。下午还有On site，求祝福一般申请条件里就要references的是给名字和联系方法吗？Anyone know Xi’an Jiaotong我们公司有个职位（在NJ）最长回文串HR 不回邮件，不回留言，怎么办~有从opt转成J2的么请教搬家的事，多谢