To solve this problem, we need to find the maximum sum of a submatrix in a given 2D matrix such that the sum is no larger than a given value ( k ). The solution extends the 1D problem of finding the maximum subarray sum ≤ ( k ) to the 2D case using prefix sums and binary search.

Approach

1. Transpose the Matrix: If the number of rows is greater than the number of columns, transpose the matrix to reduce the number of column pairs we need to consider (since the number of column pairs is ( O(n^2) ), where ( n ) is the number of columns).
2. Fix Column Pairs: For each pair of left and right columns, compute the row-wise sum of elements between these columns. This converts the 2D problem into a 1D problem where each element is the sum of a row segment.
3. 1D Maximum Subarray Sum ≤ ( k ): For the row-wise sum array, use a prefix sum and a sorted list to find the maximum subarray sum ≤ ( k ). This involves:
   • Maintaining a prefix sum array.
   • Using binary search to find the smallest prefix sum that, when subtracted from the current prefix sum, gives a sum ≤ ( k ).

Solution Code

import bisect

def maxSumSubmatrix(matrix, k):
    def max_subarray_leq(arr, k):
        max_sum = -float('inf')
        prefix = 0
        sorted_prefixes = [0]
        for num in arr:
            prefix += num
            target = prefix - k
            idx = bisect.bisect_left(sorted_prefixes, target)
            if idx < len(sorted_prefixes):
                current = prefix - sorted_prefixes[idx]
                if current > max_sum:
                    max_sum = current
            bisect.insort(sorted_prefixes, prefix)
        return max_sum

    R = len(matrix)
    if R == 0:
        return 0
    C = len(matrix[0])
    if C == 0:
        return 0

    # Transpose if rows > columns to minimize column pairs
    if R > C:
        matrix = list(zip(*matrix))
        R, C = C, R

    global_max = -float('inf')
    for left in range(C):
        row_sums = [0] * R
        for right in range(left, C):
            for i in range(R):
                row_sums[i] += matrix[i][right]
            current_max = max_subarray_leq(row_sums, k)
            if current_max > global_max:
                global_max = current_max
            # Early exit if we find the maximum possible sum (k)
            if global_max == k:
                return k
    return global_max if global_max != -float('inf') else -1

Explanation

1. Transpose: Transposing the matrix when rows are more than columns reduces the number of column pairs, optimizing the solution.
2. Row-wise Sum: For each left column, we build the row sum array by adding elements from the left to the right column. This array represents the sum of each row segment between the left and right columns.
3. Prefix Sum & Binary Search: For the row sum array, we compute the prefix sum. For each prefix sum, we find the smallest previous prefix sum that allows the current subarray sum to be ≤ ( k ) using binary search. This helps in efficiently finding the maximum valid subarray sum.

This approach efficiently handles the problem with a time complexity of ( O(\min(R, C)^2 \times \max(R, C) \log \max(R, C)) ), where ( R ) and ( C ) are the number of rows and columns in the matrix. This makes it suitable for large matrices.

Note: The function returns the maximum sum ≤ ( k ). If no valid submatrix exists, it returns -1 (adjustable based on problem constraints). Early termination is used if the sum equals ( k ) (since it's the maximum possible value).)

（免责声明：本文为本网站出于传播商业信息之目的进行转载发布，不代表本网站的观点及立场。本文所涉文、图、音视频等资料的一切权利和法律责任归材料提供方所有和承担。本网站对此资讯文字、图片等所有信息的真实性不作任何保证或承诺，亦不构成任何购买、投资等建议，据此操作者风险自担。） 本文为转载内容，授权事宜请联系原著作权人，如有侵权，请联系本网进行删除。