Maximum sum of any submatrix of a Matrix which is sorted row | C # 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 readonly 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
using System ; class GFG { static int maxSubMatSum ( int [ , ] mat ) { int n = mat . GetLength ( 0 ) ; int m = mat . GetLength ( 1 ) ; 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 } } ; Console . Write ( maxSubMatSum ( mat ) ) ; } }