本文共 792 字，大约阅读时间需要 2 分钟。

周二进行了MS的面试，一面的第二题没有做出来，当时和面试官说了，回来好好想想，然后把思路贴在博客上，虽然面试官高可能也不会来看。但是还是自己总结一下吧！题目和一样，有两种思路。

第一种思路 也就是走之前面试官提示的思路。基于假设把矩阵沿着某一行分开，然后把分开的行作为底面，将自底面往上的矩阵看成一个直方图（histogram）。直方图的中每个项的高度就是从底面行开始往上1的数量。根据Largest Rectangle in Histogram就可以求出当前行作为矩阵下边缘的一个最大矩阵。接下来如果对每一行都做一次Largest Rectangle in Histogram，从其中选出最大的矩阵，那么它就是整个矩阵中面积最大的子矩阵。 第二种思路 采用动态规划的思想。从第一行开始一行一行地处理，使[i, j]处最大子矩阵的面积是(right(i, j)-left(i, j))*height(i, j)。其中height统计当前位置及往上’1’的数量；left和right是高度是当前点的height值得左右边界，即是以当前点为中心，以height为高度向两边扩散的左右边界。

递推公式如下：

left(i, j) = max(left(i-1, j), cur_left);right(i, j) = min(right(i-1, j), cur_right);height(i, j) = height(i-1, j) + 1, if matrix[i][j]=='1';

height(i, j) = 0, if matrix[i][j]==’0’.

其中cur_left和cur_right的值由当前行决定，如果当前位置是’1’，则cur_left和cur_right都不变；如果当前位置是’0’，则cur_left就为当前位置的右侧，cur_right就为当前位置。

转载地址：http://zorvb.baihongyu.com/