Maximum sum not exceeding K possible for any rectangle of a Matrix | Python3 program for the above approach ; Function to find the maximum possible sum of arectangle which is less than K ; Stores the values ( cum_sum - K ) ; Insert 0 into the set sumSet ; Traverse over the rows ; Get cumulative sum from [ 0 to i ] ; Search for upperbound of ( cSum - K ) in the hashmap ; If upper_bound of ( cSum - K ) exists , then update max sum ; Insert cummulative value in the hashmap ; Return the maximum sum which is less than K ; Function to find the maximum sum of rectangle such that its sum is no larger than K ; Stores the number of rows and columns ; Store the required result ; Set the left column ; Set the right column for the left column set by outer loop ; Calculate sum between the current left and right for every row ; Stores the sum of rectangle ; Update the overall maximum sum ; Print the result ; Driver Code ; Function Call
from bisect import bisect_left , bisect_right NEW_LINE import sys NEW_LINE def maxSubarraySum ( sum , k , row ) : NEW_LINE INDENT curSum , curMax = 0 , - sys . maxsize - 1 NEW_LINE sumSet = { } NEW_LINE sumSet [ 0 ] = 1 NEW_LINE for r in range ( row ) : NEW_LINE INDENT curSum += sum [ r ] NEW_LINE arr = list ( sumSet . keys ( ) ) NEW_LINE it = bisect_left ( arr , curSum - k ) NEW_LINE if ( it != len ( arr ) ) : NEW_LINE INDENT curMax = max ( curMax , curSum - it ) NEW_LINE DEDENT sumSet [ curSum ] = 1 NEW_LINE DEDENT return curMax NEW_LINE DEDENT def maxSumSubmatrix ( matrix , k ) : NEW_LINE INDENT row = len ( matrix ) NEW_LINE col = len ( matrix [ 0 ] ) NEW_LINE ret = - sys . maxsize - 1 NEW_LINE for i in range ( col ) : NEW_LINE INDENT sum = [ 0 ] * ( row ) NEW_LINE for j in range ( i , col ) : NEW_LINE INDENT for r in range ( row ) : NEW_LINE INDENT sum [ r ] += matrix [ r ] [ j ] NEW_LINE DEDENT curMax = maxSubarraySum ( sum , k , row ) NEW_LINE ret = max ( ret , curMax ) NEW_LINE DEDENT DEDENT print ( ret ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT matrix = [ [ 1 , 0 , 1 ] , [ 0 , - 2 , 3 ] ] NEW_LINE K = 2 NEW_LINE maxSumSubmatrix ( matrix , K ) NEW_LINE DEDENT