text: Maximum path sum from top left to bottom right of a matrix passing through one of the given cells | C # program for the above approach ; 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: using System ; class GFG { static int [ , ] start = new int [ 3 , 3 ] ; static int [ , ] ending = new int [ 3 , 3 ] ; static void calculateStart ( int n , int m ) { for ( int i = 1 ; i < m ; ++ i ) { start [ 0 , i ] += start [ 0 , i - 1 ] ; } for ( int i = 1 ; i < n ; ++ i ) { start [ i , 0 ] += start [ i - 1 , 0 ] ; } for ( int i = 1 ; i < n ; ++ i ) { for ( int j = 1 ; j < m ; ++ j ) { start [ i , j ] += Math . Max ( start [ i - 1 , j ] , start [ i , j - 1 ] ) ; } } } static void calculateEnd ( int n , int m ) { for ( int i = n - 2 ; i >= 0 ; -- i ) { ending [ i , m - 1 ] += ending [ i + 1 , m - 1 ] ; } for ( int i = m - 2 ; i >= 0 ; -- i ) { ending [ n - 1 , i ] += ending [ n - 1 , i + 1 ] ; } for ( int i = n - 2 ; i >= 0 ; -- i ) { for ( int j = m - 2 ; j >= 0 ; -- j ) { ending [ i , j ] += Math . Max ( ending [ i + 1 , j ] , ending [ i , j + 1 ] ) ; } } } static void maximumPathSum ( int [ , ] mat , int n , int m , int q , int [ , ] coordinates ) { for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < m ; ++ j ) { start [ i , j ] = mat [ i , j ] ; ending [ i , j ] = mat [ i , j ] ; } } calculateStart ( n , m ) ; calculateEnd ( n , m ) ; int ans = 0 ; for ( int i = 0 ; i < q ; ++ i ) { int X = coordinates [ i , 0 ] - 1 ; int Y = coordinates [ i , 1 ] - 1 ; ans = Math . Max ( ans , start [ X , Y ] + ending [ X , Y ] - mat [ X , Y ] ) ; } Console . Write ( ans ) ; } public static void Main ( ) { int [ , ] mat = { { 1 , 2 , 3 } , { 4 , 5 , 6 } , { 7 , 8 , 9 } } ; int N = 3 ; int M = 3 ; int Q = 2 ; int [ , ] coordinates = { { 1 , 2 } , { 2 , 2 } } ; maximumPathSum ( mat , N , M , Q , coordinates ) ; } }