题意

给一个N*N的方阵，找出一个子矩阵，使子矩阵的和最大。(n<=100)

思路

一维的情况是经典的”最大连续和问题”。我们考虑把二维的问题降到一维来。我们枚举最高的层和最低的层，把他们中间的值都加到一个tmp数组里，然后用tmp数组来做”最大连续和问题”，不断更新ans。那么最后得出的ans一定是最大子矩阵。

代码

#include 
   
     #include 
    
      #include 
     
       using namespace std; const int INF = 1000000000; const int maxn = 110; int n; int s[maxn][maxn]; int tmp[maxn]; int dp[maxn]; int main() { scanf("%d",&n); for(int i = 0 ; i < n ; i ++) { for(int j = 0 ; j < n ; j ++) scanf("%d",&s[i][j]); } int ans = -INF; for(int i = 0 ; i < n ; i ++) { for(int j = i ; j < n ; j ++) { memset(tmp,0,sizeof(tmp)); for(int t = i ; t <= j ; t ++) { for(int c = 0 ; c < n ; c ++) tmp[c] += s[t][c]; } //对tmp dp ans = max(ans,tmp[0]); int temp = tmp[0]; for(int i = 1 ; i < n ; i ++) { if(temp <= 0) { temp = tmp[i]; }else { temp += tmp[i]; } ans = max(ans,temp); } } } printf("%d\n",ans); return 0; }