Given a matrix, mat[][] of dimensions N * M, the task is to find the maximum path sum from the top-left cell (0, 0) to all other cells of the given matrix. Only possible moves from any cell (i, j) is (i + 1, j) and (i, j + 1).
Examples:
Input: mat[][] = {{3, 2, 1}, {6, 5, 4}, {7, 8, 9}}
Output:
3 5 6
9 14 18
16 24 33
Explanation:
Path from (0, 0) to (0, 1) with maximum sum is (0, 0) ? (0, 1)
Path from (0, 0) to (0, 2) with maximum sum is (0, 0) ? (0, 1) ? (0, 2)
Path from (0, 0) to (1, 0) with maximum sum is (0, 0) ? (1, 0)
Path from (0, 0) to (1, 1) with maximum sum is (0, 0) ? (1, 0) ? (1, 1)
Path from (0, 0) to (1, 2) with maximum sum is (0, 0) ? (1, 0) ? (1, 2)
Path from (0, 0) to (2, 0) with maximum sum is (0, 0) ? (2, 0)
Path from (0, 0) to (2, 1) with maximum sum is (0, 0) ? (1, 0) ? (2, 0) ? (2, 1)
Path from (0, 0) to (2, 2) with maximum sum is (0, 0) ? (1, 0) ? (2, 0) ? (2, 1) ? (2, 2)Input: mat[][] = {{10, 20, 30}, {40, 50, 40}, {70, 80, 80}}
Output:
10 30 60
50 100 140
120 200 280
Approach: The problem can be solved using Dynamic Programming. Below is the recurrence relation to solving the problem.
Recurrence relation:
pathSum(i, j) = mat[i][j] + max(pathSum(i – 1, j), pathSum(i, j – 1))
where i > 0 and j > 0Base Case:
If i = 0 and j = 0: return mat[0][0]
If i = 0: return mat[i][j] + pathSum(i, j – 1)
If j = 0: return mat[i][j] + pathSum(i – 1, j)
Follow the steps below to solve the problem:
- Initialize the matrix dp[][], where dp[i][j] store the maximum path sum from (0, 0) to (i, j).
- Use the above-mentioned recurrence relation to compute the value of dp[i][j].
- Finally, print the value of dp[][] matrix.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;#define SZ 100// Function to get the maximum path// sum from top-left cell to all// other cells of the given matrixvoid pathSum(const int mat[SZ][SZ], int N, int M){ // Store the maximum path sum int dp[N][M]; // Initialize the value // of dp[i][j] to 0. memset(dp, 0, sizeof(dp)); // Base case dp[0][0] = mat[0][0]; for (int i = 1; i < N; i++) { dp[i][0] = mat[i][0] + dp[i - 1][0]; } for (int j = 1; j < M; j++) { dp[0][j] = mat[0][j] + dp[0][j - 1]; } // Compute the value of dp[i][j] // using the recurrence relation for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { dp[i][j] = mat[i][j] + max(dp[i - 1][j], dp[i][j - 1]); } } // Print maximum path sum from // the top-left cell for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cout << dp[i][j] << " "; } cout << endl; }}// Driver Codeint main(){ int mat[SZ][SZ] = { { 3, 2, 1 }, { 6, 5, 4 }, { 7, 8, 9 } }; int N = 3; int M = 3; pathSum(mat, N, M);} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{static final int SZ = 100;// Function to get the maximum path// sum from top-left cell to all// other cells of the given matrixstatic void pathSum(int [][]mat, int N, int M){ // Store the maximum path sum int [][]dp = new int[N][M]; // Base case dp[0][0] = mat[0][0]; for (int i = 1; i < N; i++) { dp[i][0] = mat[i][0] + dp[i - 1][0]; } for (int j = 1; j < M; j++) { dp[0][j] = mat[0][j] + dp[0][j - 1]; } // Compute the value of dp[i][j] // using the recurrence relation for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { dp[i][j] = mat[i][j] + Math.max(dp[i - 1][j], dp[i][j - 1]); } } // Print maximum path sum from // the top-left cell for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { System.out.print(dp[i][j] + " "); } System.out.println(); }}// Driver Codepublic static void main(String[] args){ int mat[][] = {{3, 2, 1}, {6, 5, 4}, {7, 8, 9}}; int N = 3; int M = 3; pathSum(mat, N, M);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 Program to implement# the above approach# Function to get the maximum path# sum from top-left cell to all# other cells of the given matrixdef pathSum(mat, N, M): # Store the maximum path sum # Initialize the value # of dp[i][j] to 0. dp = [[0 for x in range(M)] for y in range(N)] # Base case dp[0][0] = mat[0][0] for i in range(1, N): dp[i][0] = (mat[i][0] + dp[i - 1][0]) for j in range(1, M): dp[0][j] = (mat[0][j] + dp[0][j - 1]) # Compute the value of dp[i][j] # using the recurrence relation for i in range(1, N): for j in range(1, M): dp[i][j] = (mat[i][j] + max(dp[i - 1][j], dp[i][j - 1])) # Print maximum path sum # from the top-left cell for i in range(N): for j in range(M): print(dp[i][j], end = " ") print()# Driver codeif __name__ == '__main__': mat = [[3, 2, 1], [6, 5, 4], [7, 8, 9]] N = 3 M = 3 pathSum(mat, N, M)# This code is contributed by Shivam Singh |
C#
// C# program to implement// the above approachusing System;class GFG{static readonly int SZ = 100;// Function to get the maximum path// sum from top-left cell to all// other cells of the given matrixstatic void pathSum(int [,]mat, int N, int M){ // Store the maximum path // sum int [,]dp = new int[N, M]; // Base case dp[0, 0] = mat[0, 0]; for (int i = 1; i < N; i++) { dp[i, 0] = mat[i, 0] + dp[i - 1, 0]; } for (int j = 1; j < M; j++) { dp[0, j] = mat[0, j] + dp[0, j - 1]; } // Compute the value of dp[i,j] // using the recurrence relation for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { dp[i, j] = mat[i,j] + Math.Max(dp[i - 1, j], dp[i, j - 1]); } } // Print maximum path sum from // the top-left cell for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { Console.Write(dp[i, j] + " "); } Console.WriteLine(); }}// Driver Codepublic static void Main(String[] args){ int [,]mat = {{3, 2, 1}, {6, 5, 4}, {7, 8, 9}}; int N = 3; int M = 3; pathSum(mat, N, M);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to implement// the above approachlet SZ = 100;// Function to get the maximum path// sum from top-left cell to all// other cells of the given matrixfunction pathSum(mat, N, M){ // Store the maximum path sum let dp = new Array(N); // Loop to create 2D array using 1D array for (var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } // Base case dp[0][0] = mat[0][0]; for (let i = 1; i < N; i++) { dp[i][0] = mat[i][0] + dp[i - 1][0]; } for (let j = 1; j < M; j++) { dp[0][j] = mat[0][j] + dp[0][j - 1]; } // Compute the value of dp[i][j] // using the recurrence relation for (let i = 1; i < N; i++) { for (let j = 1; j < M; j++) { dp[i][j] = mat[i][j] + Math.max(dp[i - 1][j], dp[i][j - 1]); } } // Print maximum path sum from // the top-left cell for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { document.write(dp[i][j] + " "); } document.write("<br/>"); }}// Driver Code let mat = [[3, 2, 1], [6, 5, 4], [7, 8, 9]]; let N = 3; let M = 3; pathSum(mat, N, M);</script> |
3 5 6 9 14 18 16 24 33
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
