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 ; Drive Code
var start = Array . from ( Array ( 3 ) , ( ) => Array ( 3 ) ) ; var ending = Array . from ( Array ( 3 ) , ( ) => Array ( 3 ) ) ; function calculateStart ( n , m ) { for ( var i = 1 ; i < m ; ++ i ) { start [ 0 ] [ i ] += start [ 0 ] [ i - 1 ] ; } for ( var i = 1 ; i < n ; ++ i ) { start [ i ] [ 0 ] += start [ i - 1 ] [ 0 ] ; } for ( var i = 1 ; i < n ; ++ i ) { for ( var j = 1 ; j < m ; ++ j ) { start [ i ] [ j ] += Math . max ( start [ i - 1 ] [ j ] , start [ i ] [ j - 1 ] ) ; } } } function calculateEnd ( n , m ) { for ( var i = n - 2 ; i >= 0 ; -- i ) { ending [ i ] [ m - 1 ] += ending [ i + 1 ] [ m - 1 ] ; } for ( var i = m - 2 ; i >= 0 ; -- i ) { ending [ n - 1 ] [ i ] += ending [ n - 1 ] [ i + 1 ] ; } for ( var i = n - 2 ; i >= 0 ; -- i ) { for ( var j = m - 2 ; j >= 0 ; -- j ) { ending [ i ] [ j ] += Math . max ( ending [ i + 1 ] [ j ] , ending [ i ] [ j + 1 ] ) ; } } } function maximumPathSum ( mat , n , m , q , coordinates ) { for ( var i = 0 ; i < n ; ++ i ) { for ( var j = 0 ; j < m ; ++ j ) { start [ i ] [ j ] = mat [ i ] [ j ] ; ending [ i ] [ j ] = mat [ i ] [ j ] ; } } calculateStart ( n , m ) ; calculateEnd ( n , m ) ; var ans = 0 ; for ( var i = 0 ; i < q ; ++ i ) { var X = coordinates [ i ] [ 0 ] - 1 ; var Y = coordinates [ i ] [ 1 ] - 1 ; ans = Math . max ( ans , start [ X ] [ Y ] + ending [ X ] [ Y ] - mat [ X ] [ Y ] ) ; } document . write ( ans ) ; } var mat = [ [ 1 , 2 , 3 ] , [ 4 , 5 , 6 ] , [ 7 , 8 , 9 ] ] ; var N = 3 ; var M = 3 ; var Q = 2 ; var coordinates = [ [ 1 , 2 ] , [ 2 , 2 ] ] ; maximumPathSum ( mat , N , M , Q , coordinates ) ;