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

2周前 (06-26)牛客题解74

一、问题背景与算法思路

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

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

#include <iostream>
#include <vector>
#include <climits>
using namespACe std;

// 求解一维数组的最大子段和（Kadane算法）
int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0];  // 全局最大值
    int current = nums[0]; // 当前连续子数组和
    
    for(int i = 1; i < nums.size(); i++) {
        // 决策：是单独取当前元素，还是接续前面的子数组
        current = max(nums[i], current + nums[i]);
        // 更新全局最大值
        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[col] += matrix[bottom][col];
            }
            // 对列累加结果求最大子段和
            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[i][j];
        }
    }
    
    // 输出最大子矩阵和
    cout << maxSubMatrix(matrix) << endl;
    return 0;
}