最大子矩阵和的问题

文章目录

1. 1. 题目
2. 2. 最大子序列
3. 3. 最大子矩阵

题目

现有矩阵：
0, -2, -7,  0, 3
9,  2, -6,  2, 5
-4, 1, -4,  1, 6
-1, 8,  0, -2, 2
求该矩阵的一个子矩阵，使子矩阵所有元素的和最大

最大子序列

在看最大子矩阵之前，先来看一下最大子序列的求解：

给定一个长度为n的一维数组a，请找出此数组的一个子数组,使得此子数组的和sum＝a[i]+a[i+1]+……+a[j]最大（0<=i<=j<=n-1）
比如在序列-2,11,-4,13,-5,-2中，最大子序和为11+(-4)+13=19

求解该方法一般使用动态规划b[j]=max{b[j-1]+a[j],a[j]}，简化后的程序为

public static int maxSubSum(int[] a){

	int maxSum=0,curSum=0;
	for(int i=0;i<a.length;i++)
	{
		curSum+=a[i];
		if(curSum>maxSum)
		{
			maxSum=curSum;
		}else if(curSum<0)		{
		
			curSum=0;
		}
	}
	
	return maxSum;
}

该解法的复杂度为O(n)

最大子矩阵

最大子矩阵可以借鉴或者转为最大子序列

假设已经当前最大子矩阵的行数为1，那么其实就是将矩阵分解为4行分别再用子序列求解即可，
那如果子矩阵的行数为2呢？我们可以分解为{0,1}行，{1,2}行，{2,3}行求最大和即可，
以{0,1}行为例子：
0, -2, -7, 0, 3
9, 2, -6, 2, 5
再该范围内再求最大子矩阵其实就是按列求和转为一维数组再求最大：
9,0,-13,2,8
就可以知道第3，4列构成的子矩阵为最大。
将此思路扩展开到r行，求解方法为将这r行按列求和转为一维矩阵再求最大和，这里的一维矩阵其实就是子列和
所以如果当前矩阵一共有N行，再求子矩阵问题时可能出现行的情况一共有(N^2)/2种，为了计算这些情况的子列和，需要加一个辅助矩阵：全部子列和（totalColSum）
0, -2, -7, 0, 3
9, 0, -13, 2, 8
5, 1, -17, 3, 14
4, 9, -17, 1, 16

有了该辅助矩阵，我们就可以轻松求出指定列的子列和：

• 假如当前的子矩阵是{0,1}行，可直接得到子列和为9,0,-13,2,8
• 假如当前的子矩阵是{1,2}行，可通过totalColSum的第2行减去第0行的数据而得5,3,-4,3,11

所以上述思路的全部程序如下

public static int maxSubSum2D(int[][] matrix, int N, int M) {
	int sum=Integer.MIN_VALUE;
	int[][] totalColSum = new int[N][M];// 所有子列的和
	int[] subColSum=new int[M];//子列的和
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (i == 0)
				totalColSum[i][j] = matrix[i][j];
			else
				totalColSum[i][j] = totalColSum[i - 1][j] + matrix[i][j];
		}
	}

	for (int r = 0; r < N-1; r++) {
		for (int k = r; k < N; k++) {
			
			if( r==1 && k==3)
			{
				System.out.println("");
			}
				
			//构建子列
			for(int j=0;j<M;j++)
			{
				if(r==k)
				{
					subColSum[j]=matrix[r][j];//是求单行的情况
				}else if(r==0){
					subColSum[j]=totalColSum[k][j];//以0为起始行
				}else{
					subColSum[j]=totalColSum[k][j]-totalColSum[r-1][j];//以非0为起始行，需要减去前面的
				}
				
			}
			
			sum=Math.max(sum, MaxSubSum.maxSubSum(subColSum));//转为最大子段和
			
		}
	}
	
	return sum;

}

它最终的复杂度为O(N*N*M)

---

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。