【题解】最大加权矩形 —— 枚举上下界 + Kadane 降维法

核心思想：把二维最大子矩阵问题，转化为多个一维最大子段和问题！

---

先看完整代码

#include <bits/stdc++.h>
using namespace std;

// Kadane 算法：求一维数组的最大子段和
long long kadane(const vector<long long>& arr) {
    long long maxEndingHere = arr[0]; // 以当前元素结尾的最大和
    long long maxSoFar = arr[0];      // 全局最大值
    
    for (size_t i = 1; i < arr.size(); ++i) {
        // 要么接上前面，要么从当前重新开始
        maxEndingHere = max(arr[i], maxEndingHere + arr[i]);
        maxSoFar = max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}

int main() {
    int size;
    cin >> size;
    vector<vector<long long>> mat(size, vector<long long>(size));
    
    // 输入矩阵
    for (int i = 0; i < size; ++i)
        for (int j = 0; j < size; ++j)
            cin >> mat[i][j];

    long long globalMax = LLONG_MIN; // 全局答案（必须初始化为极小值！）

    // 枚举所有可能的上下边界
    for (int top = 0; top < size; ++top) {
        vector<long long> colSum(size, 0); // 动态维护从 top 到 bottom 的列和

        for (int bottom = top; bottom < size; ++bottom) {
            // 把第 bottom 行加到列和中（按列累加）
            for (int j = 0; j < size; ++j) {
                colSum[j] += mat[bottom][j];
            }

            // 对当前压缩后的一维数组跑 Kadane
            long long currentMax = kadane(colSum);
            globalMax = max(globalMax, currentMax);
        }
    }

    cout << globalMax << endl;
    return 0;
}

---

Kadane 算法就像炒股一样做决策！

Kadane 算法的本质是每天决定要不要“重开”：

🔑 核心口诀：
每天算两笔账：
① 带上昨天一起干能赚多少？（current + a[i]）
② 今天单干能赚多少？（a[i]）
选大的那个！同时记下历史最高赚了多少。

📈 举个栗子：

数组：[2, -4, 3, -1, 2, -4, 3]

步骤	当前选择	说明
第1天	2	只能选它
第2天	-2	2 + (-4) 比 -4 好
第3天	3	重开！比 -2 + 3 = 1 更好
第4天	2	3 + (-1) 继续干
第5天	4	2 + 2 → 新高！
...	...	最终答案 = 4

[？]常见疑问

Q：如果全是负数（如 [-5, -2, -8]）怎么办？
A：那就选亏得最少的那天！

• 第1天：-5 → 最高 = -5
• 第2天：max(-7, -2) = -2 → 最高 = -2
• 第3天：max(-10, -8) = -8 → 最高仍为 -2 【答案对的】

Q：为什么不能初始化 globalMax = 0？
A：因为题目要求必须选至少一个元素！如果全为负，答案不可能是 0（那等于没选），所以必须用 LLONG_MIN 或 a[0] 初始化。

---

本题思路：降维打击🥵🥵🥵！

原问题是二维最大子矩阵和，但我们可以通过以下三步解决：

1. 枚举上下边界（top 和 bottom）
   → 固定子矩阵的行范围

2. 列压缩
   → 把 top 到 bottom 行的每一列加起来，得到一维数组 colSum

3. Kadane 找左右边界
   → 在 colSum 上跑 Kadane，自动找出最优的左右列！

这样，所有可能的子矩阵都被覆盖了，而且时间复杂度仅为 $O(n^3)$，完全满足 $n \leq 120$ 的要求。

---

为什么这样能覆盖所有情况？

• 任何一个子矩阵都有唯一的上下边界 (top, bottom)
• 对每个 (top, bottom)，Kadane 会自动找出最优左右边界
• 所以无需显式枚举左右边界，Kadane 帮你在线性时间内搞定！

---

总结

• Kadane：一维最大子段和（$O(n)$）
• 枚举 + 压缩：把二维问题拆成多个一维问题（$O(n^2)$ 次）
• 总复杂度：$O(n^3)$，最稳的一集你知道吗？

这道题完美展示了 “降维 + 经典算法” 的威力！希望我的分享对你有帮助

---

💬 P.S. 如果你觉得这个思路有用，不妨点个赞！也欢迎在评论区讨论其他解法～

主播我觉得我过不了校队选拔