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
< ? php function maxAverageOfPath ( $ cost , $ N ) { $ dp = array ( array ( ) ) ; $ dp [ 0 ] [ 0 ] = $ cost [ 0 ] [ 0 ] ; for ( $ i = 1 ; $ i < $ N ; $ i ++ ) $ dp [ $ i ] [ 0 ] = $ dp [ $ i - 1 ] [ 0 ] + $ cost [ $ i ] [ 0 ] ; for ( $ j = 1 ; $ j < $ N ; $ j ++ ) $ dp [ 0 ] [ $ j ] = $ dp [ 0 ] [ $ j - 1 ] + $ cost [ 0 ] [ $ j ] ; for ( $ i = 1 ; $ i < $ N ; $ i ++ ) { for ( $ j = 1 ; $ j <= $ N ; $ j ++ ) $ dp [ $ i ] [ $ j ] = max ( $ dp [ $ i - 1 ] [ $ j ] , $ dp [ $ i ] [ $ j - 1 ] ) + $ cost [ $ i ] [ $ j ] ; } return $ dp [ $ N - 1 ] [ $ N - 1 ] / ( 2 * $ N - 1 ) ; } $ cost = array ( array ( 1 , 2 , 3 ) , array ( 6 , 5 , 4 ) , array ( 7 , 3 , 9 ) ) ; echo maxAverageOfPath ( $ cost , 3 ) ; ? >