参考dp求最大字串和的思想,将一维dp转化为二维的形式,将当前列的和当成一维的数进行dp即可。这题和求最大子矩阵和的dp思路一样。
1 class Solution { 2 public: 3 int maximalRectangle(vector<vector<char>>& matrix) { 4 int n = matrix.size(); 5 int m = matrix[0].size(); 6 7 int a[n+5][m+5]; 8 9 for(int i=0;i<m;i++){ 10 for(int j=0;j<n;j++){ 11 a[j][i]=matrix[j][i]-'0'; 12 if(j>0)a[j][i]+=a[j-1][i]; 13 } 14 } 15 16 int ans=0; 17 18 for(int i=0;i<n;i++){ 19 for(int j=i;j<n;j++){ 20 21 int b[m+5]; 22 23 24 for(int k=0;k<m;k++){ 25 if(i>0)b[k]=a[j][k]-a[i-1][k]; 26 else b[k]=a[j][k]; 27 28 if(b[k]!=j-i+1)b[k]=0; 29 else b[k]=1; 30 31 if(b[k]>0&&k>0){ 32 if(b[k-1]>0)b[k]+=b[k-1]; 33 } 34 if(b[k])ans=max(ans,(j-i+1)*b[k]); 35 } 36 37 38 } 39 } 40 return ans; 41 } 42 };
标签:size,最大,int,leetcode85,ans,矩形,dp,matrix From: https://www.cnblogs.com/ccsu-kid/p/18002779