给定一个矩阵，求和最大的子矩阵。

将每一列的值进行累加，枚举起始行和结束行，然后就可以线性优化了 复杂度O（n^3）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=301,M=301;const int INF=0x3fffffff;int sum[N][M],arr[M];int find_max(int a[N][M],int n,int m){ if(n==0||m==0)return 0; int i,j,up,down, ret=-INF; memset(sum,0,sizeof(sum)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) sum[i][j]=sum[i-1][j]+a[i][j]; arr[0]=0; for(up=1;up<=n;up++) for(down=up;down<=n;down++) { for(i=1;i<=m;i++) arr[i]=arr[i-1]+(sum[down][i]-sum[up-1][i]); int mini=0; for(i=1;i<=m;i++) { ret=max(ret,arr[i]-mini); mini=min(mini,arr[i]); } } return max(0,ret); }int main(){freopen("t.txt","r",stdin); int n; while(scanf("%d",&n)!=EOF) { int num[N][M]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&num[i][j]); printf("%d\n",find_max(num,n,n)); } return 0;}