题目描述
为了更好的备战 NOIP2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为，我们不光需要机房，我们还需要运动，于是就决定找校长申请一块电脑组的课余运动场地，听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的运动场地的面积就是你们能找到的这个最大的数字。
校长先给他们一个n*n 矩阵。要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大 。矩阵的每个元素属于 [-127,127],例如
0 –2 –7 0
9 2 –6 2
-4 1 –4 1
-1 8 0 –2
在左下角：
9 2
-4 1
-1 8
和为 15。
几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH，TZY 小朋友帮忙计算，但是遗憾的是他们的答案都不一样，涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？
输入格式
第一行：n，接下来是 n 行 n 列的矩阵。
输出格式
最大矩形（子矩阵）的和。
样例 #1
样例输入 #1
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
样例输出 #1
15
提示
1 <=n<=120
Kadane算法
这是一个经典的求解一维最大子数组和的算法，时间复杂度是 O(n)。
过程：我们遍历所有可能的左右边界（列），将这两列之间的所有行元素累加起来形成一个新的数组。
对于每一个累加的数组，应用 Kadane 算法来寻找这个一维数组的最大子数组和。
代码示例
#include <iostream>
#include <climits>
using namespace std;
// Kadane算法：求一维数组中连续子数组的最大和
int kadane(int arr[], int n) {
int max_so_far = arr[0];
int max_ending_here = 0;
for (int i = 0; i < n; i++) {
max_ending_here += arr[i];
if (max_ending_here > max_so_far) {
max_so_far = max_ending_here;
}
if (max_ending_here < 0) {
max_ending_here = 0;
}
}
return max_so_far;
}
// 求最大加权矩形的和,这是主要的求解函数，它通过枚举所有的列对 (left, right)，并将这两列之间的元素累加到 temp 数组中。然后在 temp 数组上应用 Kadane 算法，计算该区域内最大加权矩形的和。
int maxSum(int matrix[][120], int n) {
int max_sum = INT_MIN;
// 遍历所有列对 (left, right)
for (int left = 0; left < n; ++left) {
int temp[120] = {0}; // 存储每列加和后的临时数组
for (int right = left; right < n; ++right) {
// 将从left列到right列的每行元素累加到temp数组
for (int i = 0; i < n; ++i) {
temp[i] += matrix[i][right];
}
// 在temp数组上应用Kadane算法，找出最大和
int current_max = kadane(temp, n);
max_sum = max(max_sum, current_max); // 更新全局最大和
}
}
return max_sum;
}
int main() {
int n;
cin >> n;
int matrix[120][120];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> matrix[i][j];
}
}
// 输出最大加权矩形的和
cout << maxSum(matrix, n) << endl;
return 0;
}