POJ1050To the Max（求最大子矩阵）-白红宇

POJ1050To the Max（求最大子矩阵）

阅读量：5270 次

发布时间：2019-06-14

本文共 1795 字，大约阅读时间需要 5 分钟。

题意：给出N*N的矩阵，求一个子矩阵使得子矩阵中元素和最大

分析：

必备知识：求一组数的最大连续和

1    int a[N]; 2    int sum = 0,maxn = -INF; 3    for(int i = 1; i <= n; i++) 4    { 5         if(sum + a[i] > a[i]) 6             sum += a[i]; 7         else 8             sum = a[i]; 9         maxn = max(sum, maxn);10    }

一维数组最大连续和

假设要求的子矩阵位于 r 行到 i 行，c 列到 j 列之间怎么找出这个值呢？

方法：可以讲矩阵从 r 行到 i 行之间按照列求和放到一个数组中，colsum[y] 表示 y 列所有元素的和，所以对这个colsum[] 来求最大连续和就得出解来

但是不知道最大子矩阵是位于那两个行之间，需要两重循环枚举r 行到 i 行

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 const int Max = 210; 7 const int INF = 0x3f3f3f3f; 8 int matrix[Max][Max]; 9 int colsum[Max],n,maxn;10 int maxcolsum()11 {12     int ans = 0, colmax = -INF;13     for(int i = 1; i <= n; i++)14     {15         if(colsum[i] + ans > colsum[i])16             ans += colsum[i];17         else18             ans = colsum[i];19         if(colmax < ans)20             colmax = ans;21     }22     return colmax;23 }24 int maxMatrix()25 {26     for(int i = 1; i <= n; i++)27     {28         memset(colsum, 0, sizeof(colsum));29         for(int j = i; j <= n; j++)30         {31             for(int k = 1; k <= n; k++)32                 colsum[k] += matrix[j][k];  //求 从 i 行到 j 行所有的列元素的和33             int ans = maxcolsum();  // 对列元素和 求 最大连续和  34             if(maxn < ans)35                 maxn = ans;36         }37     }38     return maxn;39 }40 int main()41 {42 43     while (scanf("%d", &n) != EOF)44     {45         for(int i = 1; i <= n; i++)46             for(int j = 1; j <= n; j++)47                 scanf("%d", &matrix[i][j]);48         maxn = -INF;49         printf("%d\n",maxMatrix());50     }51     return 0;52 }