Maximum sum not exceeding K possible for any rectangle of a Matrix | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSubarraySum ( vector < int > & sum , int k , int row ) { int curSum = 0 , curMax = INT_MIN ; set < int > sumSet ; sumSet . insert ( 0 ) ; for ( int r = 0 ; r < row ; ++ r ) { curSum += sum [ r ] ; auto it = sumSet . lower_bound ( curSum - k ) ; if ( it != sumSet . end ( ) ) { curMax = max ( curMax , curSum - * it ) ; } sumSet . insert ( curSum ) ; } return curMax ; } void maxSumSubmatrix ( vector < vector < int > > & matrix , int k ) { int row = matrix . size ( ) ; int col = matrix [ 0 ] . size ( ) ; int ret = INT_MIN ; for ( int i = 0 ; i < col ; ++ i ) { vector < int > sum ( row , 0 ) ; for ( int j = i ; j < col ; ++ j ) { for ( int r = 0 ; r < row ; ++ r ) { sum [ r ] += matrix [ r ] [ j ] ; } int curMax = maxSubarraySum ( sum , k , row ) ; ret = max ( ret , curMax ) ; } } cout << ret ; } int main ( ) { vector < vector < int > > matrix = { { 1 , 0 , 1 } , { 0 , -2 , 3 } } ; int K = 2 ; maxSumSubmatrix ( matrix , K ) ; return 0 ; }