hdu1081 最大子矩阵

最大子矩阵自然直在最大连续子序列的升级版 不过其原理都是用到了动态规划思想 只是矩阵用到了枚举 +合并 把很多列看成是一列的和

#include
  
   
#include
   
     #include
     
     using namespace std
     ; #define INF -10000000 
      int n
     ,num
     [110
     ][110
     ],mark
     [110
     ]; int linemax
     () { int x
     =0
     ,i
     ,Max
     =INF
     ; for(i
     =1
     ;i
     <=n
     ;i
     ++) { if(x
     >0
     ) { x
     +=mark
     [i
     ]; } else x
     =mark
     [i
     ]; if(x
     >Max
     ) Max
     =x
     ; } return Max
     ; } int rowmax
     () { int i
     ,j
     ,k
     ; int Max
     =INF
     ; for(i
     =1
     ;i
     <=n
     ;i
     ++)//枚举所有行 { memset
     (mark
     ,0
     ,sizeof(mark
     )); for(j
     =i
     ;j
     <=n
     ;j
     ++) { for(k
     =1
     ;k
     <=n
     ;k
     ++) { mark
     [k
     ]+=num
     [j
     ][k
     ]; //列向求和 } int x
     =linemax
     ();//最大连续子序列求法求出最大值 if(x
     >Max
     ) Max
     =x
     ; } } return Max
     ; } int main() { int i
     ,j
     ; while(~scanf
     ("%d"
     ,&n
     )) { for(i
     =1
     ;i
     <=n
     ;i
     ++) for(j
     =1
     ;j
     <=n
     ;j
     ++) scanf
     ("%d"
     ,&num
     [i
     ][j
     ]); printf
     ("%d\n"
     ,rowmax
     ()); } return 0
     ; }