如何在矩阵中求最大和的子矩阵？
来源：3-3 在LeetCode上解决第一个问题 Move Zeros
河水洗回忆
2018-04-14
leetcode中53号问题是求数组中的连续子数组的最大和，如果是矩阵，那么该如何求解这个矩阵中和最大的子矩阵呢？请问波波老师有什么好的解决思路？
写回答
1回答
-
非常好的拓展。其实这是一个经典问题：）
一个标准解法是：穷举子矩阵的左边界和右边界，对于每一个左右边界，将每行左右边界的之间的元素和计算出来。之后，确定上下边界的过程等同于是连续子数组最大和的问题。
需要预处理一个sum[i][j]，表示第i行arr[i][0] 到 arr[i][j]的所有元素和，这样可以在每次穷举到一个左右边界的时候，快速计算出每行左右边界之间的元素和。比如左边界为l，右边界为r，则第i行l到r的元素和为arr[i][r] - arr[i][l-1]。
整体时间复杂度为O(n^3)，其中外层n^2用于遍历左右边界，内层n就是求解53号问题。
整体这个思想称为kadane's algorithm。其实核心是53号问题的1d表述。2d问题只是在左右边界上进行遍历，之后将2d问题转化成了1d问题。
112018-04-14
相似问题