题目描述

给出一个大小为 n x n 的矩阵，里面元素为 正整数 和 负整数 ，找到具有最大和的子矩阵。

样例

输入:

matrix = [

    [1,3,-1],

    [2,3,-2],

    [-1,-2,-3]

]

输出: 9

解释:

具有最大和的子矩阵是:

[

    [1,3],

    [2,3]

]

输入:

matrix = [

    [1,1,1],

    [1,1,1],

    [1,1,1]

]

输出: 9

解释:

具有最大和的子矩阵是:

[

    [1,1,1],

    [1,1,1],

    [1,1,1]

]

思路

与我上一篇 LintCode 41. 最大子数组 中的解法类似，只不过这题求解的是多维数组，因此我们可以先将其“压缩”一维数组。

何谓压缩？其实就是每次取一行，然后依次将下面行对应列位置的数字加上来，每次加一行，然后对所得的一位数组求解最大子数组和，最后再取所有这些和的最大值即为所求。

代码

class Solution:

    """

    @param matrix: the given matrix

    @return: the largest possible sum

    """

    def maxSubmatrix(self, matrix):

        max_sum = 0

        for row in range(len(matrix)):

            # 压缩成一位数组

            zip_matrix = [0] * len(matrix[0])

            # 将下面行对应列位置的数加到上面行

            # 从而压缩成一位数组

            for ptr in range(row, len(matrix)):

                for col in range(len(matrix[0])):

                    zip_matrix[col] += matrix[ptr][col]

                max_sum = max(max_sum, self.get_max_sub_sum(zip_matrix))

        return max_sum

    def get_max_sub_sum(self, array):

        """求一维数组的最大子数组和"""

        max_local_sum = 0

        max_global_sum = 0

        for num in array:

            max_local_sum = max(max_local_sum + num, num)

            max_global_sum = max(max_global_sum, max_local_sum)

        return max_global_sum