Path with maximum average value | method returns maximum average of all path of cost matrix ; Initialize first column of total cost ( dp ) array ; Initialize first row of dp array ; Construct rest of the dp array ; divide maximum sum by constant path length : ( 2 N - 1 ) for getting average ; Driver Code
function maxAverageOfPath ( cost , N ) { let dp = new Array ( N + 1 ) ; for ( let i = 0 ; i < N + 1 ; i ++ ) { dp [ i ] = new Array ( N + 1 ) ; for ( let j = 0 ; j < N + 1 ; j ++ ) { dp [ i ] [ j ] = 0 ; } } dp [ 0 ] [ 0 ] = cost [ 0 ] [ 0 ] ; for ( let i = 1 ; i < N ; i ++ ) dp [ i ] [ 0 ] = dp [ i - 1 ] [ 0 ] + cost [ i ] [ 0 ] ; for ( let j = 1 ; j < N ; j ++ ) dp [ 0 ] [ j ] = dp [ 0 ] [ j - 1 ] + cost [ 0 ] [ j ] ; for ( let i = 1 ; i < N ; i ++ ) for ( let j = 1 ; j < N ; j ++ ) dp [ i ] [ j ] = Math . max ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) + cost [ i ] [ j ] ; return dp [ N - 1 ] [ N - 1 ] / ( 2 * N - 1 ) ; } let cost = [ [ 1 , 2 , 3 ] , [ 6 , 5 , 4 ] , [ 7 , 3 , 9 ] ] ; document . write ( maxAverageOfPath ( cost , 3 ) ) ;