Maximum sum of any submatrix of a Matrix which is sorted row | 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 ; Given matrix mat ; Function Call
function maxSubMatSum ( mat ) { var n = mat . length ; var m = mat [ 0 ] . length ; var i , j ; var dp = Array ( n ) . fill ( ) . map ( ( ) => Array ( m ) . fill ( 0 ) ) ; dp [ n - 1 ] [ m - 1 ] = mat [ n - 1 ] [ m - 1 ] ; var 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 ; } var mat = [ [ - 6 , - 4 , - 1 ] , [ - 3 , 2 , 4 ] , [ 2 , 5 , 8 ] ] ; document . write ( maxSubMatSum ( mat ) ) ;