子矩阵的最大和

问题

给定一个无序矩阵,其中有正,有负,有 0,求子矩阵的最大和

思路

思路一：暴力枚举；已知由左上顶点坐标与右下顶点坐标可唯一确定一个子矩阵。左上顶点与右下顶点的确定分别需要O(n^2)，遍历所有子矩阵需要O(n^2)。故暴力枚举的总体时间复杂度O(n^6)。

然而利用之前学习过的算法原型，可以将时间复杂度降为O(n^3)，是不是感觉很吊，闭上眼睛小小的期待一下吧！

前几篇文章介绍过子数组最大累加和 子数组最大的累加和，如果我们将二维矩阵压缩成一维，就可以用O(n)的时间复杂度计算出子矩阵的最大和。加上遍历所有子矩阵需要的O(n^2)，故总体时间复杂度成功地降为O(n^3)

如何将二维矩阵压缩成一维数组，并转化成子数组最大累加和问题。我们将子矩阵的每一列求和，然后和值用s数组保存起来，转型成功。这也是压缩矩阵常用到的技巧

若矩阵为m*n矩阵，在矩阵的长和宽中，我们应选取数值较小的一个，作为最外层for循环的趟数

核心代码

int SubMatrixMaxSum(int m[][line])
{
    if (m == NULL || row == 0 || line == 0) {
        return 0;
    }
    //res初始化为非常小的负数
    int res = -65535;
    for (int i = 0; i < row; i++)
    {
        int* s = new int[line];
        for (int j = i; j < row; j++)
        {
            int cur = 0;
            for (int k = 0; k < line; k++)
            {
                //生成s数组
                s[k] += m[j][k];
                cur += s[k];
                res = max(res, cur);
                cur = cur < 0 ? 0 : cur;
            }
        }
    }
    return res;
}
int main()
{
    int matrix[row][line] = { { 0, -2, -7, 0}, {9, 2, -6, 2},
        {-4, 1, -4, 1}, {-1, 8, 0, -2} };
    printf("res: %d\n", SubMatrixMaxSum(matrix));
}

每一个子矩阵对应一个s数组，故在遍历的过程中，每趟都需要new一个新的s数组用来保存当前子矩阵。同理，当前和值变量cur每趟都需要初始化为0
cur = cur < 0 ? 0 : cur;可放在过程的开始或者结束，意思没有差别。

C++小知识

二维数组的传参方法，这里我们使用的是方法一，形参为指向数组的指针并给出数组长度。 具体C/C++ 语 言二维数组的传参方法总结