题意：给定一个矩阵，每个元素可正可负，求最大子矩阵使得其所有元素和最大。给定的矩阵是环形的，即：第一列和最后一列是相连接的，第一行和最后一行也是相连接的。
分析：构造前缀和。O(n4)的效率不是很满意，期待更快的算法
View Code
1 #include <stdio.h> 2 #include <iostream> 3 using namespace std; 4 const int MAXN = 160; 5 #define DEBUG 6 int a[MAXN][MAXN], b[MAXN], c[MAXN]; 7 int main(){ 8 #ifndef DEBUG 9 freopen("in.txt", "r", stdin); 10 #endif 11 int cas, n; 12 scanf("%d", &cas); 13 while(cas--){ 14 scanf("%d", &n); 15 int i, j; 16 for(i=0; i<n; i++) 17 for(j=0; j<n; j++){ 18 scanf("%d", &a[i][j]); 19 a[i][j+n]=a[i+n][j]=a[i+n][j+n]=a[i][j]; 20 } 21 int ans = -0X3F3F3F3F; 22 int x, y; 23 for(x=0; x<n; x++) 24 for(y=0; y<n; y++) 25 for(i=0; i<n; i++) 26 for(j=0; j<n; j++){ 27 c[j]=a[i+x][y+j]; 28 if(j>0) c[j]+=c[j-1]; 29 if(i>0) b[j]+=c[j]; 30 else b[j]=c[j]; 31 if(ans<b[j]) ans=b[j]; 32 } 33 printf("%d\n", ans); 34 } 35 return 0; 36 }
