text: Maximum path sum from top left to bottom right of a matrix passing through one of the given cells | Stores the maximum path sum from the cell ( 1 , 1 ) to ( N , M ) ; Stores the maximum path sum from the cell ( j , j ) to ( N , M ) ; Function to find the maximum path sum from the cell ( 1 , 1 ) to ( N , M ) ; Traverse the first row ; Traverse the first column ; Traverse the matrix ; Update the value of start [ i ] [ j ] ; Function to find the maximum path sum from the cell ( j , j ) to ( N , M ) ; Traverse the last row ; Traverse the last column ; Traverse the matrix ; Update the value of ending [ i ] [ j ] ; Function to find the maximum path sum from the top - left to the bottom right cell such that path contains one of the cells in the array coordinates [ ] [ ] ; Initialize the start and the end matrices ; Calculate the start matrix ; Calculate the end matrix ; Stores the maximum path sum ; Traverse the coordinates ; Update the value of ans ; Print the resultant maximum sum path value ; Driver Code
code: start = [ [ 0 for i in range ( 3 ) ] for j in range ( 3 ) ] NEW_LINE ending = [ [ 0 for i in range ( 3 ) ] for j in range ( 3 ) ] NEW_LINE def calculateStart ( n , m ) : NEW_LINE INDENT for i in range ( 1 , m , 1 ) : NEW_LINE INDENT start [ 0 ] [ i ] += start [ 0 ] [ i - 1 ] NEW_LINE DEDENT for i in range ( 1 , n , 1 ) : NEW_LINE INDENT start [ i ] [ 0 ] += start [ i - 1 ] [ 0 ] NEW_LINE DEDENT for i in range ( 1 , n , 1 ) : NEW_LINE INDENT for j in range ( 1 , m , 1 ) : NEW_LINE INDENT start [ i ] [ j ] += max ( start [ i - 1 ] [ j ] , start [ i ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT def calculateEnd ( n , m ) : NEW_LINE INDENT i = n - 2 NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT ending [ i ] [ m - 1 ] += ending [ i + 1 ] [ m - 1 ] NEW_LINE i -= 1 NEW_LINE DEDENT i = m - 2 NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT ending [ n - 1 ] [ i ] += ending [ n - 1 ] [ i + 1 ] NEW_LINE i -= 1 NEW_LINE DEDENT i = n - 2 NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT j = m - 2 NEW_LINE while ( j >= 0 ) : NEW_LINE INDENT ending [ i ] [ j ] += max ( ending [ i + 1 ] [ j ] , ending [ i ] [ j + 1 ] ) NEW_LINE j -= 1 NEW_LINE DEDENT i -= 1 NEW_LINE DEDENT DEDENT def maximumPathSum ( mat , n , m , q , coordinates ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( m ) : NEW_LINE INDENT start [ i ] [ j ] = mat [ i ] [ j ] NEW_LINE ending [ i ] [ j ] = mat [ i ] [ j ] NEW_LINE DEDENT DEDENT calculateStart ( n , m ) NEW_LINE calculateEnd ( n , m ) NEW_LINE ans = 0 NEW_LINE for i in range ( q ) : NEW_LINE INDENT X = coordinates [ i ] [ 0 ] - 1 NEW_LINE Y = coordinates [ i ] [ 1 ] - 1 NEW_LINE ans = max ( ans , start [ X ] [ Y ] + ending [ X ] [ Y ] - mat [ X ] [ Y ] ) NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ 1 , 2 , 3 ] , [ 4 , 5 , 6 ] , [ 7 , 8 , 9 ] ] NEW_LINE N = 3 NEW_LINE M = 3 NEW_LINE Q = 2 NEW_LINE coordinates = [ [ 1 , 2 ] , [ 2 , 2 ] ] NEW_LINE maximumPathSum ( mat , N , M , Q , coordinates ) NEW_LINE DEDENT