Given a square matrix of size N*N, where each cell is associated with a specific cost. A path is defined as a specific sequence of cells that starts from the top-left cell move only right or down and ends on bottom right cell. We want to find a path with the maximum average over all existing paths. Average is computed as total cost divided by the number of cells visited in the path.
Examples:
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
One interesting observation is, the only allowed moves are down and right, we need N-1 down moves and N-1 right moves to reach the destination (bottom rightmost). So any path from top left corner to bottom right corner requires 2N – 1 cells. In average value, the denominator is fixed and we need to just maximize numerator. Therefore we basically need to find the maximum sum path. Calculating maximum sum of path is a classic dynamic programming problem, if dp[i][j] represents maximum sum till cell (i, j) from (0, 0) then at each cell (i, j), we update dp[i][j] as below,
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];
Once we get maximum sum of all paths we will divide this sum by (2N – 1) and we will get our maximum average.
Implementation:
C++
//C/C++ program to find maximum average cost path#include <bits/stdc++.h>using namespace std;// Maximum number of rows and/or columnsconst int M = 100;// method returns maximum average of all path of// cost matrixdouble 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// valueimport 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. |
Python3
# Python program to find # maximum average cost path# Maximum number of rows # and/or columnsM = 100# method returns maximum average of # all path of cost matrixdef 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 functioncost = [[1, 2, 3], [6, 5, 4], [7, 3, 9]]print(maxAverageOfPath(cost, 3))# This code is contributed by Soumen Ghosh. |
C#
// C# Code for Path with maximum average// valueusing 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. |
PHP
<?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?> |
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> |
Output
5.200000
Time complexity: O(N2) for given input N
Auxiliary Space: O(N2) for given input N.
Method – 2: Without using Extra N*N space
We can use input cost array as a dp to store the ans. so this way we don’t need an extra dp array or no that extra space.\
One observation is that the only allowed moves are down and right, we need N-1 down moves and N-1 right moves to reach the destination (bottom rightmost). So any path from top left corner to bottom right corner requires 2N – 1 cell. In average value, the denominator is fixed and we need to just maximize numerator. Therefore we basically need to find the maximum sum path. Calculating maximum sum of path is a classic dynamic programming problem, also we don’t need any prev cost[i][j] value after calculating dp[i][j] so we can modifies the cost[i][j] value such that we don’t need extra space for dp[i][j].
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];
Below is the implementation of the above approach:
C++
// C++ program to find maximum average cost path#include <bits/stdc++.h>using namespace std;// Method returns maximum average of all path of cost matrixdouble 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 programint 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 pathimport 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 |
Python3
# Python program to find maximum average cost pathfrom typing import Listdef 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 programdef main(): cost = [[1, 2, 3], [6, 5, 4], [7, 3, 9]] print(maxAverageOfPath(cost))if __name__ == '__main__': main() |
C#
// C# program to find maximum average cost pathusing 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 matrixfunction 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 programlet cost = [[1, 2, 3], [6, 5, 4], [7, 3, 9]];console.log(maxAverageOfPath(cost))// This code is contributed by karandeep1234. |
Output
5.2
Time Complexity: O(N*N)
Auxiliary Space: O(1)
This article is contributed by Utkarsh Trivedi. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
