Path with maximum average value | JAVA Code for 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 program to test above function
class GFG { public static double maxAverageOfPath ( int cost [ ] [ ] , int N ) { int dp [ ] [ ] = new int [ N + 1 ] [ N + 1 ] ; dp [ 0 ] [ 0 ] = cost [ 0 ] [ 0 ] ; for ( int i = 1 ; i < N ; i ++ ) dp [ i ] [ 0 ] = dp [ i - 1 ] [ 0 ] + cost [ i ] [ 0 ] ; for ( int j = 1 ; j < N ; j ++ ) dp [ 0 ] [ j ] = dp [ 0 ] [ j - 1 ] + cost [ 0 ] [ j ] ; for ( int i = 1 ; i < N ; i ++ ) for ( int j = 1 ; j < N ; j ++ ) dp [ i ] [ j ] = Math . max ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) + cost [ i ] [ j ] ; return ( double ) dp [ N - 1 ] [ N - 1 ] / ( 2 * N - 1 ) ; } public static void main ( String [ ] args ) { int cost [ ] [ ] = { { 1 , 2 , 3 } , { 6 , 5 , 4 } , { 7 , 3 , 9 } } ; System . out . println ( maxAverageOfPath ( cost , 3 ) ) ; } }