题意
给你一个n*n的方正，每一个格子都一个值，问它的子矩阵的sum最大为多少
思路

其实就是枚举完上下边界之后转化成了一维求最大子段，而枚举最大子段可以使用dp优化。

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
int a[105][105];
int prefix[105][105];
int sum[105][105];
int dp[105];
int main(){
    int n, ans = -128;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			scanf("%d", &a[i][j]);
			ans = max(ans, a[i][j]);
			prefix[i][j] = prefix[i][j - 1] + a[i][j];
		}
    }
    for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			sum[i][j] = sum[i - 1][j] + prefix[i][j];
		}
    }
    for(int i = 1; i <= n; i++){
		for(int j = i; j <= n; j++){
			memset(dp, 0, sizeof(dp));
			for(int k = 1; k <= n; k++){
				dp[k] = dp[k - 1] + sum[j][k] - sum[i - 1][k] - (sum[j][k - 1] - sum[i - 1][k - 1]);
			ans = max(ans, dp[k]);
			if(dp[k] < 0) dp[k] = 0;
			}
		}
    }
    printf("%d\n", ans);
    return 0;
}