944. Maximum Submatrix
2019-07-26 本文已影响0人
鸭蛋蛋_8441
Description
Given an n x n matrix of positive and negative integers, find the submatrix with the largest possible sum.
Example
Example1
Input:
matrix = [
[1,3,-1],
[2,3,-2],
[-1,-2,-3]
]
Output: 9
Explanation:
the submatrix with the largest possible sum is:
[
[1,3],
[2,3]
]
Example2
Input:
matrix = [
[1,1,1],
[1,1,1],
[1,1,1]
]
Output: 9
Explanation:
the submatrix with the largest possible sum is:
[
[1,1,1],
[1,1,1],
[1,1,1]
]
思路：
对二维数组从列的维度求和进行了降维，matrix = [
[1,3,-1],
[2,3,-2],
[-1,-2,-3]
]
转化成[1, 3, -1] [1+2, 3+3, -1-2][1+2+3,3+3-2, -1-2-3][2,3,-2][2-1, 3-2, -2-3][-1,-2,-3]一系列一维数组，然后对降维的数组求和最大的子数组，用的是easy题中求和最大子数组的思路。
代码：
