动态规划实战：牛客3895题最大子矩阵和问题详解

15303105423

一、问题背景与算法思路

本题需要在一个n×n的矩阵中找出和最大的子矩阵。我们采用经典的"降维打击"策略，将二维矩阵问题转化为一维数组的最大子段和问题，通过动态规划高效求解。

二、完整代码实现（带详细注释）

1. #include <iostream>
   
2. #include <vector>
   
3. #include <climits>
   
4. using namespACe std;
   
5. 
   
6. // 求解一维数组的最大子段和（Kadane算法）
   
7. int maxSubArray(vector<int>& nums) {
   
8.     int maxSum = nums[0];  // 全局最大值
   
9.     int current = nums[0]; // 当前连续子数组和
   
10.    
    
11.     for(int i = 1; i < nums.size(); i++) {
    
12.         // 决策：是单独取当前元素，还是接续前面的子数组
    
13.         current = max(nums[i], current + nums[i]);
    
14.         // 更新全局最大值
    
15.         maxSum = max(maxSum, current);
    
16.     }
    
17.     return maxSum;
    
18. }
    
19. 
    
20. // 求解二维矩阵的最大子矩阵和
    
21. int maxSubMatrix(vector<vector<int>>& matrix) {
    
22.     int n = matrix.size();
    
23.     int maxSum = INT_MIN; // 初始化为最小整数值
    
24.    
    
25.     // 枚举所有可能的行范围（从上边界top到下边界bottom）
    
26.     for(int top = 0; top < n; top++) {
    
27.         vector<int> temp(n, 0); // 存储列累加结果
    
28.         
    
29.         for(int bottom = top; bottom < n; bottom++) {
    
30.             // 将当前行范围内的列累加
    
31.             for(int col = 0; col < n; col++) {
    
32.                 temp[col] += matrix[bottom][col];
    
33.             }
    
34.             // 对列累加结果求最大子段和
    
35.             int current = maxSubArray(temp);
    
36.             // 更新全局最大值
    
37.             maxSum = max(maxSum, current);
    
38.         }
    
39.     }
    
40.     return maxSum;
    
41. }
    
42. 
    
43. int main() {
    
44.     int n;
    
45.     cin >> n;
    
46.     vector<vector<int>> matrix(n, vector<int>(n));
    
47.    
    
48.     // 读取n×n矩阵
    
49.     for(int i = 0; i < n; i++) {
    
50.         for(int j = 0; j < n; j++) {
    
51.             cin >> matrix[i][j];
    
52.         }
    
53.     }
    
54.    
    
55.     // 输出最大子矩阵和
    
56.     cout << maxSubMatrix(matrix) << endl;
    
57.     return 0;
    
58. }

复制代码

三、关键算法要点

• 降维思想：通过列累加将二维问题转化为一维
• Kadane算法：O(n)时间求最大子段和
• 边界处理：正确初始化最大值(INT_MIN)
• 累加技巧：逐步累加行减少重复计算
  
  

四、复杂度分析

• 时间复杂度：O(n³) （枚举行O(n²) × Kadane算法O(n)）
• 空间复杂度：O(n) （临时数组存储列累加和）
  
  

五、常见错误提醒

• 忘记初始化maxSum为INT_MIN
• 列累加时索引错误
• 边界条件处理不当（如n=1时）
• 数据类型范围不够导致溢出
  
  

六、学习价值

通过本题可以掌握：

• 二维问题的降维处理技巧
• 动态规划的状态转移思想
• Kadane算法的精妙设计
• 矩阵问题的常见处理模式
  
  

来源：动态规划实战：牛客3895题最大子矩阵和问题详解