给定一个N*N的矩阵，计算最大子矩阵和。

给定一个N*N的矩阵，计算最大子矩阵和。

思路：

最大子段和问题可以用动态规划在O(n)内解决，该题可以借助最大子段和的解法来做。我们考虑第i行到第j行的子矩阵，可以将i ~ j行的矩阵合并为一个一维数组，即把每列对应的数相加，那么这个一维数组的最大子段和就是原子矩阵的最大和。

我们用一个二维数组p来保存矩阵的部分和，p[i][j]表示左上角是(1, 1)，(下标从1开始)， 右下角是(i, j)的矩阵中元素的和。如果我们要求i~j行、k~m列的矩阵中元素的和，我们可以通过以下式子计算得出：

sum = p[j][m] - p[j][k-1] - p[i-1][m] + p[i-1][k-1]

只需要O(1)的时间。

部分和p[i][j]要怎么计算呢？我们可以通过更小的部分和来计算得到它：

p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + a[i][j]

其中a[i][j]是矩阵中的整数。我们只需要O(n2 ) 的时间即可预处理得到所有的部分和。

所以总的时间为O(n3 )。

[cpp] view plaincopy

#include <iostream>  

#include <vector>  

using namespace std;  

const int N = 101;  

int a[N][N], p[N][N];  

int MaxRecSum(int n)  

{  

    for (int i = 0; i <= n; ++i)  

    {  

        p[i][0] = 0;  

        p[0][i] = 0;  

    }     

    for (int i = 1; i <= n; ++i)  

    {  

        for (int j = 1; j <= n; ++j)  

            p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + a[i][j];  

    }  

    int max = INT_MIN;  

    for (int i = 1; i <= n; ++i)  

    {  

        for (int j = i; j <= n; ++j)  

        {  

            int sum = 0;  

            for (int k = 1; k <= n; ++k)  

            {  

                int temp = p[j][k] - p[j][k-1] - p[i-1][k] + p[i-1][k-1];  

                if (sum > 0)  

                    sum += temp;  

                else  

                    sum = temp;  

                if (sum > max)  

                    max = sum;  

            }  

        }  

    }  

    return max;  

}  

int main()  

{  

    int n = 4;  

    int num;  

    for (int i = 1; i <= n; ++i)  

    {  

        for (int j = 1; j <= n; ++j)  

        {  

            cin >> num;  

            a[i][j] = num;  

        }  

    }  

    cout << MaxRecSum(n) << endl;  

    return 0;  

}

最后

以上就是微笑帽子为你收集整理的给定一个N*N的矩阵，计算最大子矩阵和。的全部内容，希望文章能够帮你解决给定一个N*N的矩阵，计算最大子矩阵和。所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。