12.3最大子矩阵（北京大学复试题）

12.3最大子矩阵（北京大学复试题）

王道课本P227 例12.3

本题是最大连续子序列的变种问题，需要将矩阵压缩成一维问题，当作最大连续子序列和问题来处理，再利用动态规划法问题求解dp[n]

CASE 1: i == j (矩阵matrix的i行和j行为同一行时，就是最大连续子序列问题)

CASE 2: i != j 时，可以将矩阵i行到j行压缩成一行，然后转换成一维的最大连续子序列问题来处理

#include<iostream>
#include <vector>
using namespace std;
//例12.3最大子矩阵

const int inf = INT_MAX;
int main() {
		int n;
		cin >> n;
		vector<int> dp(n);
		vector<vector<int>> matrix(n, vector<int>(n));

		for (int i = 0; i < n; i++) { //初始化矩阵数据
			for (int j = 0; j < n; j++) {
				cin >> matrix[i][j];
			}
		}
		if (n == 1) {
			cout << matrix[0][0] << endl;
			return 0;
		}
		int ans = -inf;
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {  //i要大于j，不然倒着算可能会算错
				vector<int> nums(n,0); //辅助一维数组
				if (i == j) {
					//case 1,i==j行转化成一维矩阵求最大序列和
					nums = matrix[i];	
				}
				else {
					//case 2: i!=j行， 将i行到j行压缩成为一个新的一行，再利用一维矩阵最大连续子序列和来求解该问题
					//步骤一：压缩二维矩阵为一维矩阵
					for (int m = 0; m < n; m++) {
						for (int h = i; h <= j; h++) {
							nums[m] += matrix[h][m];
						}
					}
				}
				//转换成一维矩阵求最大序列和				
				for (int k = 0; k < n; k++) {
					if (k == 0) {   //这样的写法可以避免dp[0]是最大值时候，忘记把dp[0]放进来比较一下
						dp[0] = nums[0];
					}
					else {
						dp[k] = max(nums[k], dp[k - 1] + nums[k]);
					}				
					ans = max(ans, dp[k]);
				}
			}
		}
		cout << ans << endl;
		return 0;
}