本文主要是介绍动态规划4：最大子段和问题到最大子矩阵问题（四）：最大子矩阵面积问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
上文讲的是从二维矩阵（r*c），找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大
但是这个矩形的大小不一定是最大的，现在我们来找一个最大面积的子矩阵
转自：《浅谈用极大化思想解决最大子矩形问题》
问题1：来看LeetCode上的一道题：LeetCode OJ:Maximal Rectangle
题意是：给一个只有0和1元素的矩阵，从中找出一个最大的子矩阵，满足矩阵内只包含1
这显然不是求最大子矩阵和问题，是最大子矩阵面积问题
算法思想：
对于matrix[i][j]=1，找到上边离i最远且连续的位置H，左边最靠近j的最远1的位置L，并不是离j最远的1，同样找到右边最靠近j的最远位置R，result=max{result,H*(R-L)}
如果每次都对i，j处的元素都找上面元素，左边及右边元素，重复劳动太多，可以用数组来保存
对于matrix[i][j]=1，
H[i][j]表示以第i行为子矩阵的底边的子矩阵高度，及从此元素向上连续的1的个数，有H[i][j]=H[i-1][j]+1;
L[i][j]表示左边最靠近j的最远1的位置，有L[i][j]=max{L[i-1][j],离j位置左边最远的1的位置}
R[i][j]表示右边最靠近j的最远1的位置，有R[i][j]=min{R[i-1][j],离j位置右边最远的1的位置}
else
H[i][j]=0;
L[i][j]=0;
R[i][j]=n
根据i与i-1之间的关系，可以将二维数组化为一维数组处理
class Solution {
public: int maximalRectangle(vector<vector<char> > &matrix) { if(matrix.empty())return 0; int len=matrix[0].size(); vector<int> H(len); vector<int> L(len); vector<int> R(len,len); int result=0; for(int i=0;i<matrix.size();i++){ int left=0,right=len; for(int j=0;j<len;j++){ if(matrix[i][j]=='1'){ H[j]++; L[j]=max(L[j],left); } else{ left=j+1; H[j]=0;L[j]=0;R[j]=len; } } for(int j=len-1;j>=0;j--){ if(matrix[i][j]=='1'){ R[j]=min(R[j],right); result=max(result,H[j]*(R[j]-L[j])); } else right=j; } } return result; }
};
这篇关于动态规划4：最大子段和问题到最大子矩阵问题（四）：最大子矩阵面积问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
