最大子矩阵问题

问题描述如下

给定一个 N×N 的矩阵，求其中元素和最大的子矩阵。

0	-2	-7	0
9	2	-6	2
-4	1	-4	1
-1	8	0	-2

该表中的最大子矩阵为

9	2
-4	1
-1	8

大小为 15。

分析：如果使用暴力方法解决的话，要以每一个点作为子矩阵的左上点，然后进行整个矩阵的遍历，一次遍历的时间复杂度为 O(n²)，一共有 n²个点，因此时间复杂度为 O(n⁴)。

如果进行优化呢？

这里需要用到 预处理+遍历行组合+尺取法。

要预处理什么呢，要计算出以左上角点到当前点之间形成的矩阵所包含的元素之和。

得到的表应该像这样：

0	-2	-9	-9
9	9	-4	-2
5	6	-11	-8
4	13	-4	-13

如果我们需要求这片黄色区域矩阵的元素之和时只需要用 -4-x-y+z = -4-9-4+0 = -17。

接下来我们遍历行的组合，但是当我们确定好行组合之后怎么确定其中的最大值呢？

我们需要确定矩阵的左右边界，但是如果使用双重遍历来确定的话，那么复杂度跟最先提出的暴力解法是差不多的。

这里使用尺取法（Two Points），通过推进区间的开头与结尾，求满足条件的区间方法。

① 初始化左右端点

② 不断扩大右端点

③ 如果第②步无法满足条件，则终止，否则更新结果

④ 将左端点扩大 1， 然后回到②

通过尺取法能够以 O(n) 的时间复杂度来找到满足条件的最大子矩阵。

那么总体的时间复杂度为 O(n³)。

参考代码：

#include<iostream>
using namespace std;

int **arr;
int **helper;

// 最大子矩阵包含的元素数量 
int maxElement(int **arr, int n, int m, int k){
	// helper用来保存各个元素到最上角元素之间的元素之和
	 helper = new int*[n+1];
	 for(int i = 0; i <= n; i++){
	 	helper[i] = new int[m+1];
	 }
	 for(int i = 0; i <= n; i++){
	 	for(int j = 0; j <= m; j++){
	 		helper[i][j] = 0;
		 }
	 }
	// 预处理
	for(int i = 1; i <= n; i++){
		helper[1][i] = helper[1][i-1]+arr[1][i];	
		helper[i][1] = helper[i-1][1]+arr[i][1];
	}
	for(int i = 2; i <= n; i++){
		for(int j = 2; j <= m; j++){
			helper[i][j] = helper[i-1][j]+helper[i][j-1]-helper[i-1][j-1]+arr[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cout << helper[i][j] << " ";
		}
		cout << endl;
	} 
	int result = 0;
	// 遍历
	 for(int i = 1; i <= n; i++){
	 	for(int j = i; j <= n; j++){
	 		// 尺取法 O(n) 
			for(int begin = 1, end = 1; ; ){
				// 确定右端点 
				while(end <= m && (helper[j][end]-helper[i-1][end]-helper[j][begin-1]+helper[i-1][begin-1]) <= k){
					end++;
				}
				// 更新答案 
				if((j-i+1)*(end-begin) > result){
					result = (j-i+1)*(end-begin);
				}
				if(end >= m) break;
				// 确定左端点 
				while(begin < m && (helper[j][end]-helper[i-1][end]-helper[j][begin-1]+helper[i-1][begin-1]) > k){
					begin++;
				}
			}
		 }
	 }
	 return result;
}

int main(){
	int n, m, k;
	while(cin >> n >> m >> k){
		// 创建数组
		arr = new int*[n+1];
		for(int i = 0; i <= n; i++){
			arr[i] = new int[m+1];
		} 
		// 初始化 
		for(int i = 0; i <= n; i++){
			arr[0][i] = 0;
			arr[i][0] = 0;
		}
		// 输入数据
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				cin >> arr[i][j];
			}
		} 
		// 输出最大子矩阵包含的元素数量 
		cout << maxElement(arr, n, m, k) << endl;
		// 回收数组
		for(int i = 0; i <= n; i++){
			delete []arr[i];
		} 
		delete []arr;
	}
	return 0;
} 

【END】感谢观看