class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int ans = Integer.MIN_VALUE;
// 总是枚举较小的维度
if (m > n) { // 行数大于列数，枚举上下边界，压缩列
for (int top = 0; top < m; top++) {
int[] colSum = new int[n];
for (int bottom = top; bottom < m; bottom++) {
for (int j = 0; j < n; j++) {
colSum[j] += matrix[bottom][j];
}
ans = Math.max(ans, maxSubarraySumNoLargerThanK(colSum, k));
}
}
} else { // 行数不大于列数，枚举左右边界，压缩行
for (int left = 0; left < n; left++) {
int[] rowSum = new int[m];
for (int right = left; right < n; right++) {
for (int i = 0; i < m; i++) {
rowSum[i] += matrix[i][right];
}
ans = Math.max(ans, maxSubarraySumNoLargerThanK(rowSum, k));
}
}
}
return ans;
}

// 在 arr 中寻找不超过 k 的最大子数组和
private int maxSubarraySumNoLargerThanK(int[] arr, int k) {
    TreeSet<Integer> set = new TreeSet<>();
    set.add(0);
    int prefixSum = 0;
    int max = Integer.MIN_VALUE;
    for (int num : arr) {
        prefixSum += num;
        // 寻找最小的满足 prefixSum - target <= k 的 target，即 target >= prefixSum - k
        Integer target = set.ceiling(prefixSum - k);
        if (target != null) {
            max = Math.max(max, prefixSum - target);
        }
        set.add(prefixSum);
    }
    return max;
}

}