【 声明：版权全部，转载请标明出处。请勿用于商业用途。

  联系信箱：libin493073668@sina.com】

题目链接：

题意：

给出一个仅仅包括0,1的二维矩阵。要求找到一个全为1的子矩阵。并输出子矩阵的面积

思路：

首先我们对这个矩阵进行求和

dp[i][j]表示以(1,1)为左上角。(i,j)为右下角的子矩阵的1的个数

如今我们要统计蓝色矩形的面积，如果右下角的坐标是(i,j)

此时蓝色矩形的宽与长各自是r,c

那么我们仅仅须要推断蓝色矩形内的1的个数是否与r*c相等，就能够知道这个矩形是否是全1子矩阵

那么怎么统计呢？

我们能够知道dp[i][j]是(1,1)到(i,j)的1的总个数

如果绿色矩阵的左上角是(0,0)

那么绿色矩阵的面积dp[i-r][j-c]

两个红色矩阵的面积各自是dp[i][j-c]，dp[i-r][j]

那么统计蓝色矩阵1的个数的式子便是dp[i][j]-dp[i][j-c]-dp[i-r][j]+dp[i-r][j-c]

然后我们仅仅须要以每一个1为右下角，去增大r,c便可

class Solution{public:    int maximalRectangle(vector
      
       
         >& matrix)    {        int n = matrix.size();        if(n==0) return 0;        int m = matrix[0].size();        int i,j,c;        vector
        
         
           > dp,a;        dp.resize(n+1),a.resize(n+1);        for(i = 0; i<=n; i++)        {            dp[i].resize(m+1);            a[i].resize(m+1);        }        for(i = 0; i
          
           0; i--)        {            for(j = m; j>0&&maxn
           
            =0) { if(dp[i][j]-dp[i][j-c]-dp[i-r][j]+dp[i-r][j-c]==r*c)//是全1矩阵。继续增大列 { maxn = max(maxn,r*c); c++; } else break; } while(i-r>=0&&c>0) { if(dp[i][j]-dp[i][j-c]-dp[i-r][j]+dp[i-r][j-c]==r*c)//是全1矩阵。继续增大行 { maxn = max(maxn,r*c); r++; } else//否则。降低一列再去反复推断 c--; } } } } return maxn; }};