Maximum sum not exceeding K possible for any rectangle of a Matrix | Java 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
import java . io . * ; import java . util . * ; class GFG { static int maxSubarraySum ( int [ ] sum , int k , int row ) { int curSum = 0 , curMax = Integer . MIN_VALUE ; Set < Integer > sumSet = new HashSet < Integer > ( ) ; sumSet . add ( 0 ) ; for ( int r = 0 ; r < row ; ++ r ) { curSum += sum [ r ] ; ArrayList < Integer > list = new ArrayList < Integer > ( ) ; list . addAll ( sumSet ) ; int it = Integer . MIN_VALUE ; for ( int e : list ) if ( e >= ( curSum - k ) ) { it = e ; break ; } if ( it != Integer . MIN_VALUE ) { curMax = Math . max ( curMax , curSum - it ) ; } sumSet . add ( curSum ) ; } return curMax ; } static void maxSumSubmatrix ( int [ ] [ ] matrix , int k ) { int row = matrix . length ; int col = matrix [ 0 ] . length ; int ret = Integer . MIN_VALUE ; 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 ) ; } } System . out . print ( ret ) ; } public static void main ( String [ ] args ) { int [ ] [ ] matrix = { { 5 , - 4 , - 3 , 4 } , { - 3 , - 4 , 4 , 5 } , { 5 , 1 , 5 , - 4 } } ; int K = 8 ; maxSumSubmatrix ( matrix , K ) ; } }