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 ; Driver Code ; Given matrix mat [ ] [ ] ; Function call
def maxSubMatSum ( mat ) : NEW_LINE INDENT n = len ( mat ) NEW_LINE m = len ( mat [ 0 ] ) NEW_LINE dp = [ [ 0 ] * m for _ in range ( n ) ] NEW_LINE dp [ n - 1 ] [ m - 1 ] = mat [ n - 1 ] [ m - 1 ] NEW_LINE res = dp [ n - 1 ] [ m - 1 ] NEW_LINE for i in range ( m - 2 , - 1 , - 1 ) : NEW_LINE INDENT dp [ n - 1 ] [ i ] = ( mat [ n - 1 ] [ i ] + dp [ n - 1 ] [ i + 1 ] ) NEW_LINE res = max ( res , dp [ n - 1 ] [ i ] ) NEW_LINE DEDENT for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT dp [ i ] [ m - 1 ] = ( mat [ i ] [ m - 1 ] + dp [ i + 1 ] [ m - 1 ] ) NEW_LINE res = max ( res , dp [ i ] [ m - 1 ] ) NEW_LINE DEDENT for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( m - 2 , - 1 , - 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = ( mat [ i ] [ j ] + dp [ i ] [ j + 1 ] + dp [ i + 1 ] [ j ] - dp [ i + 1 ] [ j + 1 ] ) NEW_LINE res = max ( res , dp [ i ] [ j ] ) NEW_LINE DEDENT DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ - 6 , - 4 , - 1 ] , [ - 3 , 2 , 4 ] , [ 2 , 5 , 8 ] ] NEW_LINE print ( maxSubMatSum ( mat ) ) NEW_LINE DEDENT