牛客3895题解析：动态规划求解最大子矩阵问题（分治+优化思路详解）

一、题目解读

牛客网第3895题要求求解给定二维矩阵中连续子矩阵元素的最大和。题目需处理矩阵中任意范围的子矩形，并返回其元素之和的最大值。该问题属于经典的动态规划扩展题型，需将一维最大子数组思路延伸至二维场景，考验对矩阵分治与状态递推的理解。

二、解题思路

采用“分治+动态规划”策略：

1. 一维基础：利用maxSubArray函数求解一维数组的最大子数组和（动态规划经典解法，通过维护当前元素与前缀和的最大值，实现O(n)时间复杂度）。

2. 二维扩展：在maxSubMatrix函数中，通过枚举子矩阵的上下边界（top与bottom），将每一列在区间内的元素累加为临时一维数组temp，再调用maxSubArray求解该列区间的最优解。最终遍历所有边界组合，取最大值。

3. 核心逻辑：将二维问题转化为多次一维求解，利用列累加降低计算复杂度。

三、解题步骤

1. 输入矩阵：通过cin读取n阶方阵matrix。

2. 外层循环枚举子矩阵上边界top：从0到n-1遍历，确定子矩阵顶部行。

3. 内层循环枚举下边界bottom：从top到n-1遍历，形成子矩阵的高度范围。

4. 列累加生成临时数组temp：对每一列col，在[top, bottom]区间内累加元素值，存入temp[col]。

5. 调用maxSubArray计算temp的最大子数组和：获取当前子矩阵的局部最优解。

6. 全局更新maxSum：记录所有边界组合下的最大值。

7. 输出结果：返回maxSum作为最终答案。

四、代码与注释

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

// 一维最大子数组和（动态规划）
int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0], 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
    for(int top = 0; top < n; top++) {
        vector<int> temp(n, 0); // 临时数组存储列累加和
        // 枚举下边界bottom
        for(int bottom = top; bottom < n; bottom++) {
            // 列累加：将matrix[top:bottom]区间内每列元素累加至temp
            for(int col = 0; col < n; col++) {
                temp[col] += matrix[bottom][col];
            }
            // 调用一维解法求temp的最大子数组和
            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阶矩阵
    // 输入矩阵元素
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }
    // 输出结果
    cout << maxSubMatrix(matrix) << endl;
    return 0;
}

五、总结

巧妙地将二维矩阵问题拆解为一维动态规划求解，通过枚举子矩阵边界与列累加，实现了高效的时间复杂度（O(n^3)）。该解法体现了分治思想的精髓：将复杂问题分解为子问题求解，并利用已优化的一维算法作为子模块。值得注意的是，列累加过程中需确保临时数组temp的正确初始化与更新，避免边界计算错误。此外，对于更大规模的矩阵，可进一步探索如“ Kadane算法+前缀和优化”等更高效的O(n^2)解法，但用户代码已满足题目基本要求，且逻辑清晰易懂，适合作为学习矩阵动态规划的入门案例。