Maximum sum submatrix | Function to find maximum sum submatrix ; Stores the number of rows and columns in the matrix ; Stores maximum submatrix sum ; Take each row as starting row ; Take each column as the starting column ; Take each row as the ending row ; Take each column as the ending column ; Stores the sum of submatrix having topleft index ( i , j ) and bottom right index ( k , l ) ; Iterate the submatrix row - wise and calculate its sum ; Update the maximum sum ; Prthe answer ; Driver Code
def maxSubmatrixSum ( matrix ) : NEW_LINE INDENT r = len ( matrix ) NEW_LINE c = len ( matrix [ 0 ] ) NEW_LINE maxSubmatrix = 0 NEW_LINE for i in range ( r ) : NEW_LINE INDENT for j in range ( c ) : NEW_LINE INDENT for k in range ( i , r ) : NEW_LINE INDENT for l in range ( j , c ) : NEW_LINE INDENT sumSubmatrix = 0 NEW_LINE for m in range ( i , k + 1 ) : NEW_LINE INDENT for n in range ( j , l + 1 ) : NEW_LINE INDENT sumSubmatrix += matrix [ m ] [ n ] NEW_LINE DEDENT DEDENT maxSubmatrix = max ( maxSubmatrix , sumSubmatrix ) NEW_LINE DEDENT DEDENT DEDENT DEDENT print ( maxSubmatrix ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT matrix = [ [ 0 , - 2 , - 7 , 0 ] , [ 9 , 2 , - 6 , 2 ] , [ - 4 , 1 , - 4 , 1 ] , [ - 1 , 8 , 0 , - 2 ] ] NEW_LINE maxSubmatrixSum ( matrix ) NEW_LINE DEDENT