Maximum sum not exceeding K possible for any rectangle of a Matrix | 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
function maxSubarraySum ( sum , k , row ) { let curSum = 0 , curMax = Number . MIN_VALUE ; let sumSet = new Set ( ) ; sumSet . add ( 0 ) ; for ( let r = 0 ; r < row ; ++ r ) { curSum += sum [ r ] ; let list = [ ] ; list = Array . from ( sumSet ) ; let it = list . lastIndexOf ( curSum - k ) ; if ( it > - 1 ) { curMax = Math . max ( curMax , curSum - it ) ; } sumSet . add ( curSum ) ; } return curMax ; } function maxSumSubmatrix ( matrix , k ) { let row = matrix . length ; let col = matrix [ 0 ] . length ; let ret = Number . MIN_VALUE ; for ( let i = 0 ; i < col ; ++ i ) { let sum = new Array ( row ) ; for ( let j = 0 ; j < row ; j ++ ) sum [ j ] = 0 ; for ( let j = i ; j < col ; ++ j ) { for ( let r = 0 ; r < row ; ++ r ) { sum [ r ] += matrix [ r ] [ j ] ; } let curMax = maxSubarraySum ( sum , k , row ) ; ret = Math . max ( ret , curMax ) ; } } document . write ( ret ) ; } let matrix = [ [ 1 , 0 , 1 ] , [ 0 , - 2 , 3 ] ] ; let K = 2 ; maxSumSubmatrix ( matrix , K )