算法题解:子矩阵的最大累加和问题(JAVA代码)
给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。
其中,A的子矩阵指在A中行和列均连续的一块。
输入样例
| -1 | -4 | 3 |
| 3 | 4 | -1 |
| -5 | -2 | 8 |
样例输出
10
说明:最后一列子矩阵和累加为 3+(-1)+8 = 10
输入样例
| -90 | 48 | 78 |
| 64 | -40 | 64 |
| -81 | -7 | 66 |
其中最大累加和的子矩阵为:
| 48 | 78 |
| -40 | 64 |
| -7 | 66 |
累加和为:209
算法分析
我们考虑上述第二个样例中给出的矩阵。
首先考虑只有一行的矩阵 [-90,48,78],因为只有一行,所以最大累加和就是求 nums数组 [-90,48,78] 的子数组元素最大累加和。
计算结果是将子数组 [48,78] 求累加和,结果为 126。
接下来考虑含有两行的矩阵:
| -90 | 48 | 78 |
| 64 | -40 | 64 |
这个矩阵的累加数组就是在上一步的累加数组 [-90,48,78] 的基础上,依次在每个位置上加上矩阵最新一行 [64,-40,64] 的结果,即 [-26,8,142],这个数组的最大累加和为 150。
接下来考虑含有三行的矩阵:
| -90 | 48 | 78 |
| 64 | -40 | 64 |
| -81 | -7 | 66 |
这个矩阵的累加数组就是在上一步累加数组 [-26,8,142] 的基础上,依次在每个位置上加上矩阵最新一行 [-81,-7,66] 的结果,即 [-107,1,208],这个数组的最大累加和为 209。
此时,必须从矩阵的第一行元素开始,并往下的所有子矩阵已经检查完毕,接下来从矩阵的第二行开始,继续这样的过程,含有一行的矩阵:
| 64 | -40 | 64 |
因为只有一行,所以累加数组就是 [64,-40,64],这个数组的最大累加和为 88。
接下来考虑含有两行的矩阵:
| 64 | -40 | 64 |
| -81 | -7 | 66 |
这个矩阵的累加数组就是在上一步累加数组 [64,-40,64] 的基础上,依次在每个位置上累加上矩阵最新一行 [-81,-7,66] 的结果,即 [-17,-47,130],这个数组的最大累加和为 130。
此时,必须从矩阵的第二行元素开始,并往下的所有子矩阵已经查找完毕,接下来从矩阵的第三行开始,继续这样的过程,含有一行矩阵:
| -81 | -7 | 66 |
因为只有一行,所以累加数据就是 [-81,-7,66],这个数组的最大累加和为 66。
全部过程结束,所有的子矩阵都已经考虑到了,结果为以上所有最大累加和中最大的 209。
总结回顾一下上述过程要点:
- 用求累加数组的最大累加和的方式得到每一步的最大子矩阵的累加和。
- 每一步的累加数组可以利用前一步求出的累加数组很方便地更新得到。
算法设计
package com.bean.algorithmexec;import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;public class MaxSubArrayDemo2 {/** 最大子矩阵的问题* 给定一个n*n(0<n<=100)的矩阵,请找到此矩阵的一个子矩阵,并且此子矩阵的各个元素的和最大,输出这个最大的值。* Example:* 0 -2 -7 0 * 9 2 -6 2 * -4 1 -4 1 * -1 8 0 -2 * 其中左下角的子矩阵:* 9 2 * -4 1 * -1 8 * 此子矩阵的值为9+2+(-4)+1+(-1)+8=15。* */public int maxSum(int[][] nums) {if(nums==null || nums.length==0 || nums[0].length==0) {return 0;}int max=Integer.MIN_VALUE;int cur=0;int[] arr=null;for(int i=0;i!=nums.length;i++) {arr=new int[nums[0].length];for(int j=i;j!=nums.length;j++) {cur=0;for(int k=0;k!=arr.length;k++) {arr[k]+=nums[j][k];cur+=arr[k];max=Math.max(max,cur);cur=cur<0?0:cur;}}}return max;}public static void main(String args[]) throws FileNotFoundException {MaxSubArrayDemo2 p = new MaxSubArrayDemo2();int[][] nums= {{0,-2,-7,0},{9,2,-6,2},{-4,1,-4,1},{-1,8,0,-2},};// int[][] nums= {
// {-90,48,78},
// {64,-40,64},
// {-81,-7,66}
// };int result = p.maxSum(nums);System.out.println("RESULT = "+result);}
}
采用了两组矩阵数据进行验证,程序得到了预期的运行结果。
问题变形:求子矩阵既定的累加和问题
给定一个 N x N 的矩阵和两个整数 S 和 K,写一个算法求出是否存在一个 K x K 的子矩阵,其元素和等于 S。
样例数据:
K = 2, S = 14,
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 }
输出结果为:YES
说明:
1 2
5 6
这是一个 2 x 2 的子矩阵,其元素的累加和 sum = 14
样例数据:
K = 1, S = 5,
{1, 2},
{7, 8}
输出结果为:NO
算法分析
采用动态规划算法解决此问题。
- 创建一个dp数组:dp[N + 1][N + 1], 其中 dp[i][j] 存储 行从 1到i,列从 1到j 的子矩阵所有元素的累加和。
- 一旦二维数组创建了,现在假设我们希望找到一个子矩阵,其下标从 (i, j) 到 (i + x, j + x)。这个矩阵的元素累加和可以表示为:dp[i + x][j + x] – dp[i][j + x] – dp[i + x][j] + dp[i][j]。
算法设计
package com.bean.algorithmexec;public class MaxSubArrayDemo3 {//设置一个 4*4 的矩阵static int N = 4;static int getSum(int r1, int r2, int c1, int c2, int dp[][]) {return dp[r2][c2] - dp[r2][c1] - dp[r1][c2] + dp[r1][c1];}static boolean sumFound(int K, int S, int grid[][]) {// 开辟一个dp数组int dp[][] = new int[N + 1][N + 1];// 填充 dp[][] 数组for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j] + grid[i][j];}}// 检查子矩阵是否为 k X k 的子矩阵for (int i = 0; i < N; i += K) {for (int j = 0; j < N; j += K) {int sum = getSum(i, i + K, j, j + K, dp);if (sum == S) {return true;}}}// 没有找到对应的子矩阵,其元素累加了为S,则返回false;否则返回true。return false;}public static void main(String[] args) {int grid[][] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } };int K = 2;int S = 14;if (sumFound(K, S, grid)) {System.out.println("YES");} else {System.out.println("NO");}}
}
程序输出结果:
YES