动态规划实战：牛客3895题最大子矩阵和问题详解
https://dajuwangluo.cn/zb_users/upload/2025/06/202506231750657325525574.jpg一、问题背景与算法思路本题需要在一个n×n的矩阵中找出和最大的子矩阵。我们采用经典的"降维打击"策略，将二维矩阵问题转化为一维数组的最大子段和问题，通过动态规划高效求解。二、完整代码实现（带详细注释）#include <iostream>#include <vector>
#include <climits>
using namespACe std;
// 求解一维数组的最大子段和（Kadane算法）
int maxSubArray(vector<int>& nums) {
int maxSum = nums;// 全局最大值
int current = nums; // 当前连续子数组和
for(int i = 1; i < nums.size(); i++) {
// 决策：是单独取当前元素，还是接续前面的子数组
current = max(nums, current + nums);
// 更新全局最大值
maxSum = max(maxSum, current);
}
return maxSum;
}
// 求解二维矩阵的最大子矩阵和
int maxSubMatrix(vector<vector<int>>& matrix) {
int n = matrix.size();
int maxSum = INT_MIN; // 初始化为最小整数值
// 枚举所有可能的行范围（从上边界top到下边界bottom）
for(int top = 0; top < n; top++) {
vector<int> temp(n, 0); // 存储列累加结果
for(int bottom = top; bottom < n; bottom++) {
// 将当前行范围内的列累加
for(int col = 0; col < n; col++) {
temp += matrix;
}
// 对列累加结果求最大子段和
int current = maxSubArray(temp);
// 更新全局最大值
maxSum = max(maxSum, current);
}
}
return maxSum;
}
int main() {
int n;
cin >> n;
vector<vector<int>> matrix(n, vector<int>(n));
// 读取n×n矩阵
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cin >> matrix;
}
}
// 输出最大子矩阵和
cout << maxSubMatrix(matrix) << endl;
return 0;
}三、关键算法要点
[*]降维思想：通过列累加将二维问题转化为一维
[*]Kadane算法：O(n)时间求最大子段和
[*]边界处理：正确初始化最大值(INT_MIN)
[*]累加技巧：逐步累加行减少重复计算
四、复杂度分析
[*]时间复杂度：O(n³) （枚举行O(n²) × Kadane算法O(n)）
[*]空间复杂度：O(n) （临时数组存储列累加和）
五、常见错误提醒
[*]忘记初始化maxSum为INT_MIN
[*]列累加时索引错误
[*]边界条件处理不当（如n=1时）
[*]数据类型范围不够导致溢出
六、学习价值通过本题可以掌握：
[*]二维问题的降维处理技巧
[*]动态规划的状态转移思想
[*]Kadane算法的精妙设计
[*]矩阵问题的常见处理模式
来源：动态规划实战：牛客3895题最大子矩阵和问题详解
页:
[1]