Дата је квадратна матрица величине Н*Н где је свака ћелија повезана са одређеним трошком. Путања се дефинише као специфичан низ ћелија који почиње од горње леве ћелије и креће се само десно или доле и завршава се у доњој десној ћелији. Желимо да пронађемо путању са максималним просеком за све постојеће путање. Просек се израчунава као укупна цена подељена бројем ћелија посећених на путањи. 

Примери:  

 Input : Matrix = [1 2 3   
  4 5 6   
  7 8 9]   
 Output : 5.8   
 Path with maximum average is 1 -> 4 -> 7 -> 8 -> 9   
 Sum of the path is 29 and average is 29/5 = 5.8   
 
 Једно интересантно запажање је да су једини дозвољени потези доле и десно, потребни су нам Н-1 потези надоле и Н-1 десни потези да бисмо стигли до одредишта (крајње доле). Дакле, било која путања од горњег левог до доњег десног угла захтева 2Н - 1 ћелија. У    просечан    вредност имениоца је фиксна и морамо само да максимизирамо бројилац. Због тога у основи морамо пронаћи пут максималног збира. Израчунавање максималне суме путање је класичан проблем динамичког програмирања ако дп[и][ј] представља максималан збир до ћелије (и ј) од (0 0) онда у свакој ћелији (и ј) ажурирамо дп[и][ј] као испод  
  
 for all i 1  <= i  <= N   
  dp[i][0] = dp[i-1][0] + cost[i][0];    
 for all j 1  <= j  <= N   
  dp[0][j] = dp[0][j-1] + cost[0][j];    
 otherwise    
  dp[i][j] = max(dp[i-1][j] dp[i][j-1]) + cost[i][j];    
 
 Када добијемо максималан збир свих путања, поделићемо овај збир са (2Н - 1) и добићемо наш максимални просек.   
  
    Имплементација:    
 C++   
   //C/C++ program to find maximum average cost path   #include          using     namespace     std  ;   // Maximum number of rows and/or columns   const     int     M     =     100  ;   // method returns maximum average of all path of   // cost matrix   double     maxAverageOfPath  (  int     cost  [  M  ][  M  ]     int     N  )   {      int     dp  [  N  +  1  ][  N  +  1  ];      dp  [  0  ][  0  ]     =     cost  [  0  ][  0  ];      /* Initialize first column of total cost(dp) array */      for     (  int     i     =     1  ;     i      <     N  ;     i  ++  )      dp  [  i  ][  0  ]     =     dp  [  i  -1  ][  0  ]     +     cost  [  i  ][  0  ];      /* Initialize first row of dp array */      for     (  int     j     =     1  ;     j      <     N  ;     j  ++  )      dp  [  0  ][  j  ]     =     dp  [  0  ][  j  -1  ]     +     cost  [  0  ][  j  ];      /* Construct rest of the dp array */      for     (  int     i     =     1  ;     i      <     N  ;     i  ++  )      for     (  int     j     =     1  ;     j      <=     N  ;     j  ++  )      dp  [  i  ][  j  ]     =     max  (  dp  [  i  -1  ][  j  ]      dp  [  i  ][  j  -1  ])     +     cost  [  i  ][  j  ];      // divide maximum sum by constant path      // length : (2N - 1) for getting average      return     (  double  )  dp  [  N  -1  ][  N  -1  ]     /     (  2  *  N  -1  );   }   /* Driver program to test above functions */   int     main  ()   {      int     cost  [  M  ][  M  ]     =     {     {  1       2       3  }      {  6       5       4  }      {  7       3       9  }      };      printf  (  '%f'       maxAverageOfPath  (  cost       3  ));      return     0  ;   }   
  Java   
   // JAVA Code for Path with maximum average   // value   import     java.io.*  ;   class   GFG     {          // method returns maximum average of all      // path of cost matrix      public     static     double     maxAverageOfPath  (  int     cost  [][]        int     N  )      {      int     dp  [][]     =     new     int  [  N  +  1  ][  N  +  1  ]  ;      dp  [  0  ][  0  ]     =     cost  [  0  ][  0  ]  ;          /* Initialize first column of total cost(dp)    array */      for     (  int     i     =     1  ;     i      <     N  ;     i  ++  )      dp  [  i  ][  0  ]     =     dp  [  i  -  1  ][  0  ]     +     cost  [  i  ][  0  ]  ;          /* Initialize first row of dp array */      for     (  int     j     =     1  ;     j      <     N  ;     j  ++  )      dp  [  0  ][  j  ]     =     dp  [  0  ][  j  -  1  ]     +     cost  [  0  ][  j  ]  ;          /* Construct rest of the dp array */      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  ]  ;          // divide maximum sum by constant path      // length : (2N - 1) for getting average      return     (  double  )  dp  [  N  -  1  ][  N  -  1  ]     /     (  2     *     N     -     1  );      }          /* Driver program to test above function */      public     static     void     main  (  String  []     args  )         {      int     cost  [][]     =     {{  1       2       3  }      {  6       5       4  }      {  7       3       9  }};          System  .  out  .  println  (  maxAverageOfPath  (  cost       3  ));      }   }   // This code is contributed by Arnav Kr. Mandal.   
  C#   
   // C# Code for Path with maximum average   // value   using     System  ;   class     GFG     {          // method returns maximum average of all      // path of cost matrix      public     static     double     maxAverageOfPath  (  int     []  cost        int     N  )      {      int     []  dp     =     new     int  [  N  +  1    N  +  1  ];      dp  [  0    0  ]     =     cost  [  0    0  ];          /* Initialize first column of total cost(dp)    array */      for     (  int     i     =     1  ;     i      <     N  ;     i  ++  )      dp  [  i       0  ]     =     dp  [  i     -     1    0  ]     +     cost  [  i       0  ];          /* Initialize first row of dp array */      for     (  int     j     =     1  ;     j      <     N  ;     j  ++  )      dp  [  0       j  ]     =     dp  [  0    j     -     1  ]     +     cost  [  0       j  ];          /* Construct rest of the dp array */      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  ];          // divide maximum sum by constant path      // length : (2N - 1) for getting average      return     (  double  )  dp  [  N     -     1       N     -     1  ]     /     (  2     *     N     -     1  );      }          // Driver Code      public     static     void     Main  ()         {      int     []  cost     =     {{  1       2       3  }      {  6       5       4  }      {  7       3       9  }};          Console  .  Write  (  maxAverageOfPath  (  cost       3  ));      }   }   // This code is contributed by nitin mittal.   
  JavaScript   
    <  script  >      // JavaScript Code for Path with maximum average value          // method returns maximum average of all      // path of cost matrix      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  ];          /* Initialize first column of total cost(dp)    array */      for     (  let     i     =     1  ;     i      <     N  ;     i  ++  )      dp  [  i  ][  0  ]     =     dp  [  i  -  1  ][  0  ]     +     cost  [  i  ][  0  ];          /* Initialize first row of dp array */      for     (  let     j     =     1  ;     j      <     N  ;     j  ++  )      dp  [  0  ][  j  ]     =     dp  [  0  ][  j  -  1  ]     +     cost  [  0  ][  j  ];          /* Construct rest of the dp array */      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  ];          // divide maximum sum by constant path      // length : (2N - 1) for getting average      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  ));    <  /script>   
  PHP   
      // Php program to find maximum average cost path    // method returns maximum average of all path of    // cost matrix    function   maxAverageOfPath  (  $cost     $N  )   {   $dp   =   array  (  array  ())   ;   $dp  [  0  ][  0  ]   =   $cost  [  0  ][  0  ];   /* Initialize first column of total cost(dp) array */   for   (  $i   =   1  ;   $i    <   $N  ;   $i  ++  )   $dp  [  $i  ][  0  ]   =   $dp  [  $i  -  1  ][  0  ]   +   $cost  [  $i  ][  0  ];   /* Initialize first row of dp array */   for   (  $j   =   1  ;   $j    <   $N  ;   $j  ++  )   $dp  [  0  ][  $j  ]   =   $dp  [  0  ][  $j  -  1  ]   +   $cost  [  0  ][  $j  ];   /* Construct rest of the dp array */   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  ];   }   // divide maximum sum by constant path    // length : (2N - 1) for getting average    return   $dp  [  $N  -  1  ][  $N  -  1  ]   /   (  2  *  $N  -  1  );   }   // Driver code   $cost   =   array  (  array  (  1     2     3  )   array  (   6     5     4  )   array  (  7     3     9  )   )   ;   echo   maxAverageOfPath  (  $cost     3  )   ;   // This code is contributed by Ryuga   ?>   
  Python3   
   # Python program to find    # maximum average cost path   # Maximum number of rows    # and/or columns   M   =   100   # method returns maximum average of    # all path of cost matrix   def   maxAverageOfPath  (  cost     N  ):   dp   =   [[  0   for   i   in   range  (  N   +   1  )]   for   j   in   range  (  N   +   1  )]   dp  [  0  ][  0  ]   =   cost  [  0  ][  0  ]   # Initialize first column of total cost(dp) array   for   i   in   range  (  1     N  ):   dp  [  i  ][  0  ]   =   dp  [  i   -   1  ][  0  ]   +   cost  [  i  ][  0  ]   # Initialize first row of dp array   for   j   in   range  (  1     N  ):   dp  [  0  ][  j  ]   =   dp  [  0  ][  j   -   1  ]   +   cost  [  0  ][  j  ]   # Construct rest of the dp array   for   i   in   range  (  1     N  ):   for   j   in   range  (  1     N  ):   dp  [  i  ][  j  ]   =   max  (  dp  [  i   -   1  ][  j  ]   dp  [  i  ][  j   -   1  ])   +   cost  [  i  ][  j  ]   # divide maximum sum by constant path   # length : (2N - 1) for getting average   return   dp  [  N   -   1  ][  N   -   1  ]   /   (  2   *   N   -   1  )   # Driver program to test above function   cost   =   [[  1     2     3  ]   [  6     5     4  ]   [  7     3     9  ]]   print  (  maxAverageOfPath  (  cost     3  ))   # This code is contributed by Soumen Ghosh.   
    
  Излаз   
5.200000  
 
    Временска сложеност    : О(Н   2   ) за  дати унос Н   
    Помоћни простор:    О(Н   2   ) за дати улаз Н.  
  
    Метод - 2: Без коришћења додатног Н*Н простора     
  
 
 Можемо користити низ улазних трошкова као дп за чување анс. тако да нам на овај начин није потребан додатни дп низ или тај додатни простор.  
  
 
 Једно запажање је да су једини дозвољени потези доле и десно, потребни су нам Н-1 потези надоле и Н-1 десни потези да бисмо стигли до одредишта (крајње доле). Дакле, било која путања од горњег левог до доњег десног угла захтева 2Н - 1 ћелију. У    просечан    вредност имениоца је фиксна и морамо само да максимизирамо бројилац. Због тога у основи морамо пронаћи пут максималног збира. Израчунавање максималне суме путање је класичан проблем динамичког програмирања, такође нам није потребна никаква прев цост[и][ј] вредност након израчунавања дп[и][ј] тако да можемо да изменимо вредност цост[и][ј] тако да нам не треба додатни простор за дп[и][ј].  
  
 for all i 1  <= i  < N   
  cost[i][0] = cost[i-1][0] + cost[i][0];    
 for all j 1  <= j  < N   
  cost[0][j] = cost[0][j-1] + cost[0][j];    
 otherwise    
  cost[i][j] = max(cost[i-1][j] cost[i][j-1]) + cost[i][j];    
 
 Испод је примена горњег приступа:  
 C++   
   // C++ program to find maximum average cost path   #include          using     namespace     std  ;   // Method returns maximum average of all path of cost matrix   double     maxAverageOfPath  (  vector   <  vector   <  int  >>  cost  )   {      int     N     =     cost  .  size  ();      // Initialize first column of total cost array      for     (  int     i     =     1  ;     i      <     N  ;     i  ++  )      cost  [  i  ][  0  ]     =     cost  [  i  ][  0  ]     +     cost  [  i     -     1  ][  0  ];      // Initialize first row of array      for     (  int     j     =     1  ;     j      <     N  ;     j  ++  )      cost  [  0  ][  j  ]     =     cost  [  0  ][  j     -     1  ]     +     cost  [  0  ][  j  ];      // Construct rest of the array      for     (  int     i     =     1  ;     i      <     N  ;     i  ++  )      for     (  int     j     =     1  ;     j      <=     N  ;     j  ++  )      cost  [  i  ][  j  ]     =     max  (  cost  [  i     -     1  ][  j  ]     cost  [  i  ][  j     -     1  ])     +     cost  [  i  ][  j  ];      // divide maximum sum by constant path      // length : (2N - 1) for getting average      return     (  double  )  cost  [  N     -     1  ][  N     -     1  ]     /     (  2     *     N     -     1  );   }   // Driver program   int     main  ()   {      vector   <  vector   <  int  >>     cost     =     {{  1       2       3  }      {  6       5       4  }      {  7       3       9  }      };      cout      < <     maxAverageOfPath  (  cost  );      return     0  ;   }   
  Java   
   // Java program to find maximum average cost path   import     java.io.*  ;   class   GFG     {      // Method returns maximum average of all path of cost      // matrix      static     double     maxAverageOfPath  (  int  [][]     cost  )      {      int     N     =     cost  .  length  ;      // Initialize first column of total cost array      for     (  int     i     =     1  ;     i      <     N  ;     i  ++  )      cost  [  i  ][  0  ]     =     cost  [  i  ][  0  ]     +     cost  [  i     -     1  ][  0  ]  ;      // Initialize first row of array      for     (  int     j     =     1  ;     j      <     N  ;     j  ++  )      cost  [  0  ][  j  ]     =     cost  [  0  ][  j     -     1  ]     +     cost  [  0  ][  j  ]  ;      // Construct rest of the array      for     (  int     i     =     1  ;     i      <     N  ;     i  ++  )      for     (  int     j     =     1  ;     j      <     N  ;     j  ++  )      cost  [  i  ][  j  ]     =     Math  .  max  (  cost  [  i     -     1  ][  j  ]        cost  [  i  ][  j     -     1  ]  )      +     cost  [  i  ][  j  ]  ;      // divide maximum sum by constant path      // length : (2N - 1) for getting average      return     (  double  )  cost  [  N     -     1  ][  N     -     1  ]     /     (  2     *     N     -     1  );      }      // Driver program      public     static     void     main  (  String  []     args  )      {      int  [][]     cost      =     {     {     1       2       3     }     {     6       5       4     }     {     7       3       9     }     };      System  .  out  .  println  (  maxAverageOfPath  (  cost  ));      }   }   // This code is contributed by karandeep1234   
  C#   
   // C# program to find maximum average cost path   using     System  ;   class     GFG     {      // Method returns maximum average of all path of cost      // matrix      static     double     maxAverageOfPath  (  int  [     ]     cost  )      {      int     N     =     cost  .  GetLength  (  0  );      // Initialize first column of total cost array      for     (  int     i     =     1  ;     i      <     N  ;     i  ++  )      cost  [  i       0  ]     =     cost  [  i       0  ]     +     cost  [  i     -     1       0  ];      // Initialize first row of array      for     (  int     j     =     1  ;     j      <     N  ;     j  ++  )      cost  [  0       j  ]     =     cost  [  0       j     -     1  ]     +     cost  [  0       j  ];      // Construct rest of the array      for     (  int     i     =     1  ;     i      <     N  ;     i  ++  )      for     (  int     j     =     1  ;     j      <     N  ;     j  ++  )      cost  [  i       j  ]     =     Math  .  Max  (  cost  [  i     -     1       j  ]      cost  [  i       j     -     1  ])      +     cost  [  i       j  ];      // divide maximum sum by constant path      // length : (2N - 1) for getting average      return     (  double  )  cost  [  N     -     1       N     -     1  ]     /     (  2     *     N     -     1  );      }      // Driver program      static     void     Main  (  string  []     args  )      {      int  [     ]     cost      =     {     {     1       2       3     }     {     6       5       4     }     {     7       3       9     }     };      Console  .  WriteLine  (  maxAverageOfPath  (  cost  ));      }   }   // This code is contributed by karandeep1234   
  JavaScript   
   // Method returns maximum average of all path of cost matrix   function     maxAverageOfPath  (  cost  )   {      let     N     =     cost  .  length  ;      // Initialize first column of total cost array      for     (  let     i     =     1  ;     i      <     N  ;     i  ++  )      cost  [  i  ][  0  ]     =     cost  [  i  ][  0  ]     +     cost  [  i     -     1  ][  0  ];      // Initialize first row of array      for     (  let     j     =     1  ;     j      <     N  ;     j  ++  )      cost  [  0  ][  j  ]     =     cost  [  0  ][  j     -     1  ]     +     cost  [  0  ][  j  ];      // Construct rest of the array      for     (  let     i     =     1  ;     i      <     N  ;     i  ++  )      for     (  let     j     =     1  ;     j      <=     N  ;     j  ++  )      cost  [  i  ][  j  ]     =     Math  .  max  (  cost  [  i     -     1  ][  j  ]     cost  [  i  ][  j     -     1  ])     +     cost  [  i  ][  j  ];      // divide maximum sum by constant path      // length : (2N - 1) for getting average      return     (  cost  [  N     -     1  ][  N     -     1  ])     /     (  2.0     *     N     -     1  );   }   // Driver program   let     cost     =     [[  1       2       3  ]      [  6       5       4  ]      [  7       3       9  ]];   console  .  log  (  maxAverageOfPath  (  cost  ))   // This code is contributed by karandeep1234.   
  Python3   
   # Python program to find maximum average cost path   from   typing   import   List   def   maxAverageOfPath  (  cost  :   List  [  List  [  int  ]])   ->   float  :   N   =   len  (  cost  )   # Initialize first column of total cost array   for   i   in   range  (  1     N  ):   cost  [  i  ][  0  ]   =   cost  [  i  ][  0  ]   +   cost  [  i   -   1  ][  0  ]   # Initialize first row of array   for   j   in   range  (  1     N  ):   cost  [  0  ][  j  ]   =   cost  [  0  ][  j   -   1  ]   +   cost  [  0  ][  j  ]   # Construct rest of the array   for   i   in   range  (  1     N  ):   for   j   in   range  (  1     N  ):   cost  [  i  ][  j  ]   =   max  (  cost  [  i   -   1  ][  j  ]   cost  [  i  ][  j   -   1  ])   +   cost  [  i  ][  j  ]   # divide maximum sum by constant path   # length : (2N - 1) for getting average   return   cost  [  N   -   1  ][  N   -   1  ]   /   (  2   *   N   -   1  )   # Driver program   def   main  ():   cost   =   [[  1     2     3  ]   [  6     5     4  ]   [  7     3     9  ]]   print  (  maxAverageOfPath  (  cost  ))   if   __name__   ==   '__main__'  :   main  ()   
    
  Излаз   
5.2  
 
    Временска сложеност:    О(Н*Н)   
    Помоћни простор:    О(1)