題目見這里。

這個題目就是枚舉搜索，找最大值。以行為例，在每一行中找到每一個左邊界，然后枚舉以該左邊界為邊界的線段，這是第一步，然后以該線段長度分別向上和向下掃描，找到上邊界和下邊界，然后求值，如果當前值比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，如果是，則繼續(xù)向上掃描。以[0,1]-[0,1]為例，上邊界就是當前值，無需繼續(xù)掃描，對于下邊界，首先看[1,1]-[1,1]，這個范圍內(nèi)的點都是1，則滿足，然后繼續(xù)掃描，即[x,1]-[x,1]，枚舉x從0到3，看這個范圍內(nèi)的點是否都為1，一直到不滿足條件為止。

這就是基本思路，但是搜索中需要在2個地方優(yōu)化。首先是枚舉線段長度，這個可以通過一次預(yù)處理來優(yōu)化，而不是每次都需要從左到右統(tǒng)計，用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]為線段右邊界時，該線段的最大長度。

然后就是上下掃描優(yōu)化，注意我們需要求的是該線段向上和向下分別最多能覆蓋多少。如果以某一列為例，會發(fā)現(xiàn)有這樣的特性：比如在求上邊界時，如果index[i-1][j]大于index[i][j]，說明[i,j]這個線段上邊界一定不會在[i-1,j]的上邊界的下面，就是說長線段一定能覆蓋短線段。還是以上面的矩陣為例，比如index[3][3]為1，index[2][3]為3，那么[3,3]的上邊界一定是在[2,3]的上邊界的上面。而且這個過程可以循環(huán)下去，一直到找到上邊界為止。

這個優(yōu)化同并查集的路徑優(yōu)化很類似，就是比如知道A > B，同時B > C，那么我們可以推出A > C一樣。這樣就可以把一列的上下邊界在O(m)時間內(nèi)全部解決，比單純的掃描方式提升了一個數(shù)量級。代碼如下：

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;
    }
}

最后面就是對每一個矩陣進行枚舉求大小，找最大值即可。