Maximum sum of any submatrix of a Matrix which is sorted row | Java program for the above approach ; Function that finds the maximum Sub - Matrix Sum ; Number of rows in the matrix ; Number of columns in the matrix ; dp [ ] [ ] matrix to store the results of each iteration ; Base Case - The largest element in the matrix ; To stores the final result ; Find the max sub matrix sum for the last row ; Check whether the current sub - array yields maximum sum ; Calculate the max sub matrix sum for the last column ; Check whether the current sub - array yields maximum sum ; Build the dp [ ] [ ] matrix from bottom to the top row ; Update sum at each cell in dp [ ] [ ] ; Update the maximum sum ; Return the maximum sum ; Driver Code ; Given matrix mat [ ] [ ] ; Function Call
class GFG { static int maxSubMatSum ( int [ ] [ ] mat ) { int n = mat . length ; int m = mat [ 0 ] . length ; int i , j ; int [ ] [ ] dp = new int [ n ] [ m ] ; dp [ n - 1 ] [ m - 1 ] = mat [ n - 1 ] [ m - 1 ] ; int res = dp [ n - 1 ] [ m - 1 ] ; for ( i = m - 2 ; i >= 0 ; i -- ) { dp [ n - 1 ] [ i ] = mat [ n - 1 ] [ i ] + dp [ n - 1 ] [ i + 1 ] ; res = Math . max ( res , dp [ n - 1 ] [ i ] ) ; } for ( i = n - 2 ; i >= 0 ; i -- ) { dp [ i ] [ m - 1 ] = mat [ i ] [ m - 1 ] + dp [ i + 1 ] [ m - 1 ] ; res = Math . max ( res , dp [ i ] [ m - 1 ] ) ; } for ( i = n - 2 ; i >= 0 ; i -- ) { for ( j = m - 2 ; j >= 0 ; j -- ) { dp [ i ] [ j ] = mat [ i ] [ j ] + dp [ i ] [ j + 1 ] + dp [ i + 1 ] [ j ] - dp [ i + 1 ] [ j + 1 ] ; res = Math . max ( res , dp [ i ] [ j ] ) ; } } return res ; } public static void main ( String [ ] args ) { int [ ] [ ] mat = { { - 6 , - 4 , - 1 } , { - 3 , 2 , 4 } , { 2 , 5 , 8 } } ; System . out . print ( maxSubMatSum ( mat ) ) ; } }