363.Max Sum of Rectangle No Larger Than K

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

然后不断更新这个最大值。

这道题目，如果扫描列，

time complexity: O(col * col * row * log(row))

space complexity: O(col)

当 col 远大于 row 时，这么做就不合理了。

有两种方法来解决。

第一，直接按行来扫描。

第二，顺时针旋转整个矩阵 90度，然后拿原算法进行计算。

https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/discuss/83599/

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        if(matrix.length == 0){
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int maxSum = Integer.MIN_VALUE;

        //outer loop should use smaller axis
        //now we assume we have more rows than cols, therefore outer loop will be based on cols 
        for(int left = 0; left < n; left++){
            //array that accumulate sums for each row from left to right 
            int[] sums = new int[m];
            for(int right = left; right < n; right++){
                for(int i = 0; i < m; i++){
                    sums[i] += matrix[i][right];
                } 

                //we use TreeSet to help us find the rectangle with maxSum <= k with O(logN) time
                TreeSet<Integer> set = new TreeSet<Integer>();
                set.add(0);
                int currSum = 0;
                for(int sum : sums){
                    currSum += sum;
                    //we use sum subtraction (curSum - sum) to get the subarray with sum <= k
                    //therefore we need to look for the smallest sum >= currSum - k
                    Integer num = set.ceiling(currSum - k);
                    if(num != null){
                        maxSum = Math.max(maxSum, currSum - num);
                    }
                    set.add(currSum);
                }
            }
        }
        return maxSum;
    }
}