题解 | #最大子矩阵#

#include <climits>
#include <iostream>
#include <cstring>

using namespace std;

/*

暴力解：
枚举每个左上角（a,b）于右下角（c，d）
用前缀和，时间复杂度：O（n^4） 10^8

sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]

子矩阵abcd的和：
ans = sum[c][d]-sum[a-1][d]-sum[c][b-1]+sum[a-1][b-1]

const int N = 110;
int arr[N][N];
int sum[N][N];

int main() {
    int n;
    cin >> n;
    memset(arr, 0, sizeof(arr));
    memset(sum, 0, sizeof(sum));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }
    //计算前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
        }
    }
    //计算最大子矩阵和
    int ans = INT_MIN;
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            for (int c = a; c <= n; c++) {
                for (int d = b; d <= n; d++) {
                    ans = max(ans, sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1]);
                }
            }
        }
    }
    cout << ans << endl;


    return 0;
}*/




/*最优解：
枚举i行，j行来确定最大子矩阵所在的行范围
而对于列来说，把一列看成一个元素，用动态规划解决最大子序列和

时间复杂度：O（n^3） 10^6

前缀和：sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j]

子矩阵abcd的和：
ans = sum[c][d]-sum[a-1][d]-sum[c][b-1]+sum[a-1][b-1]
*/
const int N = 110;
int arr[N][N];
int sum[N][N];

int dp[N];

int main() {
    int n;
    cin >> n;
    memset(arr, 0, sizeof(arr));
    memset(sum, 0, sizeof(sum));
    memset(dp,0,sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }
    //计算前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
        }
    }
    //计算最大子矩阵和
    int ans = INT_MIN;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            for(int k=1;k<=n;k++){
                //得到每一列的子矩阵和
                int subM = sum[j][k]-sum[i-1][k]-sum[j][k-1]+sum[i-1][k-1];
                dp[k]=max(dp[k-1]+subM,subM);
                ans=max(ans,dp[k]);
            }
        }
    }
    cout << ans << endl;


    return 0;
}