https://www.luogu.com.cn/problem/P1719

法1.二维前缀和（四重循环，n^4级别）

#include <bits/stdc++.h>
#define debug(x) cout << "!" << (x) <<"!"<<endl;
#define INF 0x3f3f3f3f
#define int long long

using namespace std;
const int N = 150;
int g[N][N] , s[N][N];
int n;

signed main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++){
            cin >> g[i][j];
            s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + g[i][j];
        }
    }
    int maxx = -INF;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++){
            for(int l = i ; l <= n ; l++){
                for(int r = j ; r <= n ; r++){
                    maxx = max(maxx,s[l][r] - s[l][j-1] - s[i-1][r] + s[i-1][j-1]);
                }
            }
        }
    }
    cout << maxx;
}

法2.行遍历+列dp（三重循环，n^3）

#include <bits/stdc++.h>
#define debug(x) cout << "!" << (x) <<"!"<<endl;
#define INF 0x3f3f3f3f
#define int long long

using namespace std;
const int N = 150;
int g[N][N] , s[N][N];
int n;
int dp[N];

signed main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++){
            cin >> g[i][j];
            s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + g[i][j];
        }
    }
    int maxx = -INF;
    for(int i = 1 ; i <= n ; i++){
        for(int j = i ; j <= n ; j++){
            memset(dp,0,sizeof dp);
            dp[0] = -INF;
            for(int k = 1 ; k <= n ; k++){
                int temp = s[j][k] - s[j][k-1] - s[i-1][k] + s[i-1][k-1];
                dp[k] = max(temp,dp[k-1]+temp);
                maxx = max(maxx,dp[k]);
            }
        }
    }
    cout << maxx;
}

法3. 仅对法二的求temp做了更改，相当于一个n维列前缀和（对每一列单独前缀和）(没啥区别)

#include <bits/stdc++.h>
#define debug(x) cout << "!" << (x) <<"!"<<endl;
#define INF 0x3f3f3f3f
#define int long long

using namespace std;
const int N = 150;
int g[N][N] , temp[N][N];
int n;
int dp[N];

signed main(){
    cin >> n;
    //先读第一行
    for(int i = 1 ; i <= n ; i++){
        cin >> temp[i][1];
    }
    for(int i = 2 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++){
            cin >> g[i][j];
            temp[j][i] = temp[j][i-1] + g[i][j];
        }
    }
    int maxx = -INF;
    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++){
                int t = temp[k][j] - temp[k][i-1];
                dp[k] = max(dp[k-1]+t,t);
                maxx = max(dp[k],maxx);
            }
        }
    }
    cout << maxx;
}