Leetcode - Max Sum of Rectangle

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