Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.

It is guaranteed that there will be a rectangle with a sum no larger than k.

&nbsp;
Example 1:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).


Example 2:

Input: matrix = [[2,2,-1]], k = 3
Output: 3


&nbsp;
Constraints:


	m == matrix.length
	n == matrix[i].length
	1 &lt;= m, n &lt;= 100
	-100 &lt;= matrix[i][j] &lt;= 100
	-105 &lt;= k &lt;= 105


&nbsp;
Follow up: What if the number of rows is much larger than the number of columns?

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        import numpy as np
        
        matrix = np.array(matrix, dtype=np.int32)
        
        M,N = matrix.shape
        
        ret = float("-inf")
        
        CUM = np.zeros((M,N), dtype=np.int32)
        for shift_r in range(M):
            CUM[:M-shift_r] += matrix[shift_r:]
            
            _CUM = np.zeros((M-shift_r,N), dtype=np.int32)
            for shift_c in range(N):
                _CUM[:, :N-shift_c] += CUM[:M-shift_r,shift_c:]
                tmp = _CUM[(_CUM<=k) & (_CUM>ret)]
                if tmp.size:
                    ret = tmp.max()
            if ret == k:
                return ret
        
        return ret

'''
class Solution {
    public int maxSumSubmatrix(int[][] matrix, int tar) {
        int n=matrix.length,m=matrix[0].length,i,j,k,l,dp[][] = new int[n][m],val,max=Integer.MIN_VALUE,target=tar;
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                dp[i][j]=matrix[i][j];
                if(j>0) dp[i][j]+=dp[i][j-1];
            }
        }
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                if(i>0) dp[i][j]+=dp[i-1][j];
            }
        }
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                for(k=i;k<n;k++){
                    for(l=j;l<m;l++){
                        val=dp[k][l];
                        if((i-1)>=0 && (j-1)>=0) val += dp[i-1][j-1];
                        if((i-1)>=0) val=val-dp[i-1][l];
                        if((j-1)>=0) val=val-dp[k][j-1];
                        if(val>max && val<=target) max=val;
                    }
                }
            }
        }
        return max;
    }
}
class Solution {
public:

    // function for finding maximum subarray having sum less than k

    int find_max(vector<int>& arr, int k)
    {
        int n = arr.size();

        int maxi = INT_MIN;

        // curr_sum will store cumulative sum

        int curr_sum = 0;

        // set will store the prefix sum of array

        set<int> s;

        // put 0 into set, if curr_sum == k, (curr_sum - k) will be zero

        s.insert(0);

        for(int i = 0; i < n; i++)
        {
            // calculate cumulative sum

            curr_sum += arr[i];

            // find the prefix sum in set having sum == curr_sum - k

            auto it = s.lower_bound(curr_sum - k);

            // if prefix sum is present, update the maxi

            if(it != s.end())
            {
                maxi = max(maxi, curr_sum - *it);
            }

            // insert prefix sum into set

            s.insert(curr_sum);
        }

        return maxi;
    }

    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {

        int n = matrix.size();

        int m = matrix[0].size();

        int maxi = INT_MIN;

        // fix the position two two rows and take cumulative sum of columns between two fixed rows

        for(int start_row = 0; start_row < n; start_row++)
        {
            vector<int> col_array(m, 0);

            for(int end_row = start_row; end_row < n; end_row++)
            {
                // take cumulative sum of columns between two fixed rows

                for(int col = 0; col < m; col++)
                {
                    col_array[col] += matrix[end_row][col];
                }

                // find maximum subarray having sum less than equal to k

                int curr_max = find_max(col_array, k);

                // update the maximum sum

                maxi = max(maxi, curr_max);
            }
        }

        return maxi;
    }
};
/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var maxSumSubmatrix = function(matrix, k) {
    if (!matrix.length) return 0;

    let n = matrix.length, m = matrix[0].length;
    let sum = new Array(n + 1).fill(0).map(a => new Array(m + 1).fill(0));
    let ans = -Infinity;

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            sum[i][j] = matrix[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
            for(let x = 1; x <= i; ++x) {
                for(let y = 1; y <= j; ++y) {
                    let s = rangeSum(sum, x, y, i, j);
                    if (s <= k) {
                        ans = Math.max(s, ans);
                    }
                }
            }
        }
    }
    return ans;
}

const rangeSum = (sum, x1, y1, x2, y2) => {
    return sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
}
Max Sum of Rectangle No Larger Than K