算法标签

动态规划：通过动态规划的方法计算不同子矩形的和，并找出最大和的子矩形，这是解决此问题的核心算法思想。 二维数组处理：对二维数组进行遍历和操作，包括按行处理数组元素以及计算子矩形的和。 枚举：枚举不同的子矩形范围，即枚举所有可能的子矩形来找到最大和的子矩形。

解题思路

数据读取：

首先读取输入的整数 N，它表示二维数组的大小。 接着读取 N^2 个整数，并将它们按行存储在一个 N×N 的二维数组 matrix 中。

算法核心（最大子矩形和的计算）：

由于子矩形可能从任意行开始，我们需要枚举子矩形的起始行 i 和结束行 j。 对于每一对起始行 i 和结束行 j，我们将这几行的数据压缩成一行（即将这几行对应列的元素相加）。例如，对于一个从第 i 行到第 j 行的子矩形，我们将这 j - i + 1 行的每一列元素相加，得到一个长度为 N 的一维数组 temp。 然后，对这个一维数组 temp 使用动态规划来计算最大子数组和。动态规划的思路是，设 dp[k] 表示以 temp[k] 结尾的最大子数组和，状态转移方程为 dp[k] = max(dp[k - 1] + temp[k], temp[k])，通过遍历 temp 数组得到最大子数组和 max_sum。 在枚举所有可能的起始行 i 和结束行 j 后，我们记录下最大的 max_sum，这个 max_sum 就是最大子矩形的和。

输出结果：

最后输出找到的最大子矩形的和。

代码实现

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,dp[110],a[110][110];
int Max()
{
    int b = 0,res=-130;
    for(int i=1;i<=n;i++){
        if(b>0)b+=dp[i];// 表示能如果遇到正数还能继续递增
        else b = dp[i];//如果是负数 由于负数只能越加越小 所以那么直接让他等于当前元素
        res = max(res,b);//最优化结果
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);
    }

    int res=-130;
    for(int i=1;i<=n;i++){
        for(int j = i;j<=n;j++){
            for(int k=1;k<=n;k++)dp[k]+=a[j][k];
            int ma = Max();
            res = max(ma,res);  
        }
        memset(dp,0,sizeof(dp));
    }

    printf("%d\n",res);

    return 0;
}