題目描述
給出一個(gè)大小為?n x n?的矩陣瘤泪，里面元素為?正整數(shù)?和?負(fù)整數(shù)?掠械，找到具有最大和的子矩陣微王。
樣例
輸入:
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. 最大子數(shù)組?中的解法類(lèi)似累提，只不過(guò)這題求解的是多維數(shù)組，因此我們可以先將其“壓縮”一維數(shù)組。
何謂壓縮送滞？其實(shí)就是每次取一行侠草，然后依次將下面行對(duì)應(yīng)列位置的數(shù)字加上來(lái)，每次加一行犁嗅，然后對(duì)所得的一位數(shù)組求解最大子數(shù)組和边涕，最后再取所有這些和的最大值即為所求。
代碼
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)):
? ? ? ? ? ? # 壓縮成一位數(shù)組
? ? ? ? ? ? zip_matrix = [0] * len(matrix[0])
? ? ? ? ? ? # 將下面行對(duì)應(yīng)列位置的數(shù)加到上面行
? ? ? ? ? ? # 從而壓縮成一位數(shù)組
? ? ? ? ? ? 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):
? ? ? ? """求一維數(shù)組的最大子數(shù)組和"""
? ? ? ? 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
