题解
最大子矩阵
1 条题解
-
0
#include<bits/stdc++.h> using namespace std; #define N 105 #define INF 0x3f3f3f3f int n, a[N][N], b[N], s[N][N];//b[j]:子矩阵第j列的加和 s[i][j]:第j列的第1行到第i行的元素加和 int mx = -INF; int main() { cin >> n; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) { cin >> a[i][j]; s[i][j] = s[i-1][j] + a[i][j]; } for(int i1 = 1; i1 <= n; ++i1)//子矩阵第一行为原矩阵的第i1行,最后一行为原矩阵的第i2行 for(int i2 = i1; i2 <= n; ++i2) { for(int j = 1; j <= n; ++j) b[j] = s[i2][j] - s[i1-1][j]; int sum = 0; for(int j = 1; j <= n; ++j)//双指针法求最大子段和 { if(sum < 0) sum = b[j]; else sum += b[j]; mx = max(mx, sum); } } cout << mx; return 0; }
- 1