【题解】最大加权矩形 —— 枚举上下界 + KADANE 降维法
> 核心思想：把二维最大子矩阵问题，转化为多个一维最大子段和问题！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
先看完整代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
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(n3)O(n^3)O(n3)，完全满足 n≤120n \leq 120n≤120 的要求。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
为什么这样能覆盖所有情况？
* 任何一个子矩阵都有唯一的上下边界 (top, bottom)
* 对每个 (top, bottom)，Kadane 会自动找出最优左右边界
* 所以无需显式枚举左右边界，Kadane 帮你在线性时间内搞定！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
总结
* Kadane：一维最大子段和（O(n)O(n)O(n)）
* 枚举 + 压缩：把二维问题拆成多个一维问题（O(n2)O(n^2)O(n2) 次）
* 总复杂度：O(n3)O(n^3)O(n3)，最稳的一集你知道吗？
这道题完美展示了 “降维 + 经典算法” 的威力！希望我的分享对你有帮助
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> 💬 P.S. 如果你觉得这个思路有用，不妨点个赞！也欢迎在评论区讨论其他解法～
主播我觉得我过不了校队选拔
