My code:
import java.util.TreeSet;
public class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int m = matrix.length;
int n = matrix[0].length;
for (int i = 0; i < n; i++) {
int[] sum = new int[m];
for (int j = i; j < n; j++) {
for (int p = 0; p < m; p++) {
sum[p] += matrix[p][j];
}
int cum = 0;
TreeSet<Integer> set = new TreeSet<Integer>();
set.add(0);
for (int p = 0; p < m; p++) {
cum += sum[p];
Integer value = set.ceiling(cum - k);
if (value != null) {
if (max < cum - value) {
max = cum - value;
}
}
set.add(cum);
}
}
}
return max;
}
public static void main(String[] args) {
Solution test = new Solution();
int[][] matrix = new int[][]{{2,2,-1}};
int ret = test.maxSumSubmatrix(matrix, 0);
System.out.println(ret);
}
}
reference:
https://discuss.leetcode.com/topic/48875/accepted-c-codes-with-explanation-and-references
自己没做出来，一开始就放弃了。的确很难。
这道题目可以拆成至少两道题，最多三道题。
1 . 给你一个 matrix, 找出和最大的那个矩形，返回最大和，以及这个矩形的边界。
https://www.youtube.com/watch?v=yCQN096CwWM
这个阿三的视频讲的实在是太棒了。
time complexity: O(col * col * row)
space complexity: O(col)
思想就是DP，以列为单位，一列一列的累加，同时，对于累加起来的这一列。我们从上到下扫描他，找出其中连续的一段子数列，他的和最大。这就是大矩形下的一个子矩形， 他的和最大。
再和当前最大的和比较，如果更大，那么就更新当前最大和，同时更新当前最大矩阵的边界。
2 . 给你一个一维 array, 找出其中连续的一段，其和最大，但是不大于 k
https://www.quora.com/Given-an-array-of-integers-A-and-an-integer-k-find-a-subarray-that-contains-the-largest-sum-subject-to-a-constraint-that-the-sum-is-less-than-k
time complexity: O(n log n)
space: O(n)
我需要一个 TreeSet 的配合。
我有个变量 cum 用来累加每一个元素的和。然后去询问 Treeset,
.ceiling(cum - k), 是否存在这一个累加和， cum - 它之后，的值，小于等于 k
如果存在，拿出来，算出和 cum的差值，这就是其中一段子数列的和，并且这个和，小于等于 k
然后不断更新这个最大值。
3 . 这道题目，如果扫描列，
time complexity: O(col * col * row * log(row))
space complexity: O(col)
当 col 远大于 row 时，这么做就不合理了。
有两种方法来解决。
第一，直接按行来扫描。
第二，顺时针旋转整个矩阵 90度，然后拿原算法进行计算。
这道题目差不多就介绍到这里了。挺有意思的。
By the way, KMP 算法还记得是什么吗？
Anyway, Good luck, Richardo! -- 09/21/2016
