题解 | #最大子矩阵#

//采用暴力搜索，为O(n^4)
#include "stdio.h"
#include "climits"
using namespace std;
int N;int sum[102][102];

int main(){
    scanf("%d",&N);
    int temp;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            scanf("%d",&temp);
            sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+temp;//计算二位前缀和，不然用array会超时
        }
    }
    int Max = INT_MIN;//记录子矩阵的最大值
    //暴力搜索，4层循环，前两层找左上角(x,y)后两层找右下角(i，j)
    for (int x = 1; x <= N; ++x) {
        for (int y = 1; y <= N; ++y) {//(x,y)
            for (int i = x; i <= N; ++i) {
                for (int j = y; j <= N; ++j) {//(i,j)
                    temp = sum[i][j]-sum[i][y-1]-sum[x-1][j]+sum[x-1][y-1];//计算当前子矩阵的大小
                    if(temp > Max)
                        Max = temp;
                }
            }
        }
    }
    printf("%d",Max);
}