题目见这里。
这个题目就是枚举搜索，找最大值。以行为例，在每一行中找到每一个左边界，然后枚举以该左边界为边界的线段，这是第一步，然后以该线段长度分别向上和向下扫描，找到上边界和下边界，然后求值，如果当前值比max大，则更新max。比如下面矩阵：
0 1 1 1
0 1 1 1
1 1 1 1
1 1 0 1
以第一行为例，左边界为[0,1]，以该点为左边界的线段有3个：[0,1]-[0,1]，[0,1]-[0,2]，[0,1]-[0,3]，对于每一个线段，分别看上边界和下边界，看相邻上一行此范围的点是否都为1，如果是，则继续向上扫描。以[0,1]-[0,1]为例，上边界就是当前值，无需继续扫描，对于下边界，首先看[1,1]-[1,1]，这个范围内的点都是1，则满足，然后继续扫描，即[x,1]-[x,1]，枚举x从0到3，看这个范围内的点是否都为1，一直到不满足条件为止。
这就是基本思路，但是搜索中需要在2个地方优化。首先是枚举线段长度，这个可以通过一次预处理来优化，而不是每次都需要从左到右统计，用index[i][j]记录如下：
for (i = 0; i < m; ++i)
{
for(cur = 0, j = 0; j < n; ++j)
{
if (matrix[i][j] == 0)
index[i][j] = cur = 0;
else
index[i][j] = ++ cur;
}
}
index[i][j]中记录的就是以[i,j]为线段右边界时，该线段的最大长度。
然后就是上下扫描优化，注意我们需要求的是该线段向上和向下分别最多能覆盖多少。如果以某一列为例，会发现有这样的特性：比如在求上边界时，如果index[i-1][j]大于index[i][j]，说明[i,j]这个线段上边界一定不会在[i-1,j]的上边界的下面，就是说长线段一定能覆盖短线段。还是以上面的矩阵为例，比如index[3][3]为1，index[2][3]为3，那么[3,3]的上边界一定是在[2,3]的上边界的上面。而且这个过程可以循环下去，一直到找到上边界为止。
这个优化同并查集的路径优化很类似，就是比如知道A > B，同时B > C，那么我们可以推出A > C一样。这样就可以把一列的上下边界在O(m)时间内全部解决，比单纯的扫描方式提升了一个数量级。代码如下：
for(i = 0; i < n; ++i)
{
for(j = 0; j < m; ++j)
{
up[j] = j;
while(up[j] > 0 && index[up[j]-1][i] >= index[j][i])
up[j] = up[up[j]-1];
}
for(j = m-1; j >= 0; --j)
{
down[j] = j;
while(down[j]+1 < m && index[down[j]+1][i] >= index[j][i])
down[j] = down[down[j]+1];
}
for(j = 0; j < m; ++j)
{
cur = (down[j] - up[j] + 1) * index[j][i];
if(cur > max)
max = cur;
}
}
最后面就是对每一个矩阵进行枚举求大小，找最大值即可。
