dp优化
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int s[N][N];
int main()
{
int n; cin >> n;
for(int i = 1 ; i <= n ; i ++ )
for(int j = 1 ; j <= n ; j ++ )
{
int x; cin >> x;
s[i][j] = s[i-1][j] + x;
}
int res = -0x3f3f3f3f;
for(int i = 1 ; i <= n ; i ++ )
for(int j = i ; j <= n ; j ++ )
{
int f = 0;
for(int k = 1 ; k <= n ; k ++ )
{
f = max(0, f) + s[j][k] - s[i-1][k];
res = max(res, f);
}
}
cout << res << endl;
return 0;
}
二维前缀和
$O(n^4)$
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 110;
int g[N][N], pre[N][N];
signed main()
{
int n; cin >> n;
for(int i = 1 ; i <= n ; i ++ )
for(int j = 1 ; j <= n ; j ++ )
cin >> g[i][j];
for(int i = 1 ; i <= n ; i ++ )
for(int j = 1 ; j <= n ; j ++ )
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + g[i][j];
int ans = -1e18;
for(int i = 1 ; i <= n ; i ++ )
for(int j = 1 ; j <= n ; j ++ )
for(int k = i ; k <= n ; k ++ )
for(int w = j ; w <= n ; w ++ )
ans = max(ans, pre[k][w] - pre[i-1][w] - pre[k][j-1] + pre[i-1][j-1]);
cout << ans << endl;
return 0;
}