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
using System ; using System . Collections . Generic ; class GFG { static int maxSubarraySum ( int [ ] sum , int k , int row ) { int curSum = 0 , curMax = Int32 . MinValue ; HashSet < int > sumSet = new HashSet < int > ( ) ; sumSet . Add ( 0 ) ; for ( int r = 0 ; r < row ; ++ r ) { curSum += sum [ r ] ; List < int > list = new List < int > ( ) ; list . AddRange ( sumSet ) ; int it = list . LastIndexOf ( curSum - k ) ; if ( it > - 1 ) { curMax = Math . Max ( curMax , curSum - it ) ; } sumSet . Add ( curSum ) ; } return curMax ; } static void maxSumSubmatrix ( int [ , ] matrix , int k ) { int row = matrix . GetLength ( 0 ) ; int col = matrix . GetLength ( 1 ) ; int ret = Int32 . MinValue ; for ( int i = 0 ; i < col ; ++ i ) { int [ ] sum = new int [ row ] ; 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 = Math . Max ( ret , curMax ) ; } } Console . Write ( ret ) ; } static public void Main ( ) { int [ , ] matrix = { { 1 , 0 , 1 } , { 0 , - 2 , 3 } } ; int K = 2 ; maxSumSubmatrix ( matrix , K ) ; } }