面积最大的全1子矩阵

题目见这里。

这个题目就是枚举搜索，找最大值。以行为例，在每一行中找到每一个左边界，然后枚举以该左边界为边界的线段，这是第一步，然后以该线段长度分别向上和向下扫描，找到上边界和下边界，然后求值，如果当前值比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;
    }
}

最后面就是对每一个矩阵进行枚举求大小，找最大值即可。