//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 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# 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+1N+1];  dp[00] = cost[00];    /* Initialize first column of total cost(dp)  array */  for (int i = 1; i < N; i++)  dp[i 0] = dp[i - 10] + cost[i 0];    /* Initialize first row of dp array */  for (int j = 1; j < N; j++)  dp[0 j] = dp[0j - 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[ij - 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. 

<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 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 ?> 

# 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. 

// 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 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# 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 

// 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. 

# 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()