题意 给你一个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; }