1.求某個矩陣a[m][n]的子矩陣的最大和
思路：語文表達能力有限，下面舉例說明
假設一個矩陣a[4][5]={
{3,4,2,1,-5},
{2,2,5,-6,4},
{-5,2,1,3,3},
{-3,4,-2,-2,3}
}

建立一個輔助數組sum[m*(m+1)/2][n]，分別記錄遍歷行組合的每一列的和：
sum[1][i] = {3,4,2,1,-5}
//若子矩陣被包含于第一行，則其各列累加和為sum[1],此時只需求累加和最大的子數組即可，故子矩陣最大累加和為3+4+2+1=10
sum[2][i] = {5,6,7,-5,-1{}
//若子矩陣被包含于第一行和第二行，則其各列累加和為sum[2],此時子矩陣最大累加和為5+6+7=18
sum[3][i] = {0,8,8,-2,2}
//若子矩陣被包含于第一行、第二行和第三行，則其各列累加和為sum[3],此時子矩陣最大累加和為0+8+8+(-2)+2=16
依次類推，sum[4]表示子矩陣被包含于前四行，sum[5]表示只被包于含第二行，sum[6]表示只被包含于第二行和第三行，等等
即：1，12，123，1234，12345，2，23，234，2345，3，34，345，4，45，5
之后即可在sum中找出累加和最大的子矩陣之和
時間復雜度為O(m2*n)，即若m<n時，記錄列累加和，若m>n,則輔助數組記錄行累加和

也可以依據要求減小輔助數組的空間

public static int MaxSum(int[][] m){if(m == null || m.length == 0|| m[0].length == 0){return 0;}int max = Integer MIN_VALUE;int cur = 0;int[] s = null;for(int i = 0;i !=m.length;i++){s = new int[m[0].length];for(int j = i; j!=m.length;j++){cur = 0;for(int k = 0; k!= s.length;k++){s[k] += m[j][k];cur += s[k];max = Math.max(max, cur);cur = cur < 0 ? 0 : cur;}}}return max; }
2.給定一個無序矩陣，給定一個值k，求累加和小于等于k的最大子矩陣大小，矩陣大小用其中的元素個數來表示
思路：
假設有一個數組，給定一個值k，求累加和小于等于k的最長子數組長度，假設必須以j位置為子數組的結尾位置，從開始位置累加至j位置為sum[j]，并且sum[j]>=k，則必定有一個位置i<j,使得sum[i]>=sum[j]-k,（注，此時i位置為最早的sum[i]>=k的位置）則必須以j位置結尾的子數組且和小于等于k的最長長度為j-i。遍歷數組即可求解。


舉例：
a[] = {3,-1,2,-1,4,-2,5}
sum[] = {3,2,4,3,7,5,9}//累加和數組
max[] = {3,3,4,4,7,7,9}//累加和的區域最大值數組
在max數組中使用二分法即可求出第一個大于等于k的位置,即可按照上述思路求解

public static int max SubMatrixSumLessThank(int[][] m, int sum){//在數組中求小于等于sum值的最長的長度if(m == null || m.length == 0 || m[0] == null || m[0].length == 0){return 0;}int res = 0;for(int i = 0; i<m.length;i++){int[] sumArr = new int[m[0].length];for(int j = i; j<m.length;j++){for(int k = 0;k <m[0].length;k++){sumArr[k] += m[j][k];}res = Math.max(res, (j-i+1)*maxLength(sumArr, sum));}}return res; }public static int maxLength(int[] arr, int k){int[] h = new int(arr.length + 1);int sum = 0;h[0] = sum;for(int i = 0; i!= arr.length;i++){//累加的遞增數組sum+=arr[i];h[j+1] = Math.max(sum,h[i]);}sum = 0;int res = 0;int pre = 0;int len = 0;for(int i = 0;i != arr.length;i++){//以每個位置結尾的最長長度sum += arr[i];pre = getLessIndex(h, sum-k);len = pre == -1 ? 0 : i - pre + 1;res = Math.max(les, len);}return res; }public static int getLessIndex(int[] arr, int num){int low = 0;int high = arr.length -1;int mid = 0;int res = -1;while(low <= high){mid = (low + high)/2;if(arr[mid] >= num){res = mid;high = mid -1;}else{low = mid +1;}}return res; }
3.給定一個無序矩陣，其中只有1，0兩種值，求只含有1的最大子矩陣大小，矩陣大小用其中的元素個數來表示
時間復雜度O(m*n)
依次遍歷必須以每一行為底的矩陣的最大子矩陣大小
a[5][5]={
{0,1,1,0,1},
{1,1,0,1,1},
{1,0,0,1,1},
{0,1,1,0,0},
{1,1,0,1,1}
}
s[0] = {0,1,1,0,1}
s[1] = {1,2,0,1,2}
s[2] = {2,0,0,2,3}
s[3] = {0,1,1,0,0}
s[4] = {1,2,0,1,1}
即形成一個直方圖，依次求最大的矩形
假設一個直方圖為{3，4，5，4，3，2}
建立一個大頂棧，首先3進棧，接下來進棧4，由于4>3，則4直接進棧，同理5也進棧，由于4<=5，則開始計算當前棧頂的5，因為當前的4是5的右邊的第一個小于等于5的數，即右邊界為4，棧頂的下面的數，一定是第一個左邊的比棧頂小于等于的數，故棧頂5下面的4，是左邊界，5出棧
在實際情況下，該棧中壓入的是index

public static int maxRecSize(int[][] map){if(map == null || map.length == 0 || map[0].length == 0){return 0;}int maxArea = 0;int[] height = new int[map[0].length];for(int i = 0; i<map.length; i++){for(int j = 0; j < map[0].length; j++){height[j] = map[i][j] == 0 ? 0: height[j] + 1;}maxArea = Math.max(maxArea, maxRecFromBotton(height));}return maxArea; } public static int maxRecFromBottom(int[] height){if(height == null || height.length == 0){return 0;}int maxArea = 0;Stack<Integer> stack = new Stack<Integer>();for(int i = 0; i < height.length; i++){while(!stack.isEmpty() && height[i] <= height[stack.peek()]){int j = stack.pop();int k = stack.isEmpty() ? -1: stack.peek();int curArea = (i - k - 1) * height[j];maxArea = Math.max(maxArea, curArea);}stack.push(i);}while(!stack.isEmpty()){int j = stack.pop();int k = stack.isEmpty() ? -1: stack.peek();int curArea = (height.length - k -1) * height[j];maxArea = Math.max(maxArea, curArea);}return maxArea; }

總結

以上是生活随笔為你收集整理的有关子矩阵最大累加和的总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。