Given a matrix mat[][] of dimensions N * M and a set of coordinates of cell coordinates[][] of size Q, the task is to find the maximum sum of a path from the top-left cell (1, 1) to the bottom-right cell (N, M), such that the path should contain at least one of the coordinates from the array coordinates[][2]. The only moves allowed from any cell (i, j) of the matrix are (i + 1, j) or (i, j + 1).
Examples:
Input: mat[][ = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, coordinates[][] = {{1, 2}, {2, 2}}
Output: 27
Explanation:
The path having the maximum is given by:
(1, 1) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3).
The above path passes through the coordinates (2, 2). Therefore, the sum of the path is given by (1 + 4 + 5 + 8 + 9) = 27, which is maximum path.Input: mat[][] = {{1, 3}, {6, 7}, {8, 9}} , coordinates[][2] = {{1, 1}}
Output: 24
Naive Approach: The simplest approach to solve the given problem is to generate all possible paths from the top-left to the bottom-right cell of the matrix and print the maximum sum of cells of that path whose at least one of the coordinates in the path lies in the array coordinates[][].
Time Complexity: O((N + M)!)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by using Dynamic Programming. Consider the two matrices start[][] and end[][] such that start[i][j] denotes the maximum path sum from the cell (1, 1) to the cell (i, j) and end[i][j] denotes the maximum path sum from the cell (i, j) to the cell (N, M). Therefore, for any coordinate (X, Y), the maximum path sum can be calculated as:
start[X][Y] + end[X][Y] – mat[X][Y]
Follow the steps below to solve the problem:
- Initialize two matrices, say start[][] and end[][] of dimensions N*M such that start[i][j] denotes the maximum path sum from the cell (1, 1) to the cell (i, j) and end[i][j] denotes the maximum path sum from the cell (i, j) to the cell (N, M).
- Initialize a variable, say ans as INT_MIN that stores the resultant maximum sum.
- Calculate the maximum path sum from the cell (1, 1) to each cell (i, j) using the Bottom-Up Approach discussed in this article and store it in the matrix start[][].
- Calculate the maximum path sum from the cell (N, M) to each cell (i, j) using the Top-Down Approach discussed in this article and store it in the matrix end[][].
- Traverse the array coordinates[][] and for each coordinate (X, Y) update the value of ans as the maximum of ans and (start[X][Y] + end[X][Y] – mat[X][Y]).
- After completing the above steps, print the value of ans as the resultant maximum sum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Stores the maximum path sum from the // cell (1, 1) to (N, M) int start[3][3]; // Stores the maximum path sum from the // cell (j, j) to (N, M) int ending[3][3]; // Function to find the maximum path // sum from the cell (1, 1) to (N, M) void calculateStart( int n, int m) { // Traverse the first row for ( int i = 1; i < m; ++i) { start[0][i] += start[0][i - 1]; } // Traverse the first column for ( int i = 1; i < n; ++i) { start[i][0] += start[i - 1][0]; } // Traverse the matrix for ( int i = 1; i < n; ++i) { for ( int j = 1; j < m; ++j) { // Update the value of // start[i][j] start[i][j] += max(start[i - 1][j], start[i][j - 1]); } } } // Function to find the maximum path // sum from the cell (j, j) to (N, M) void calculateEnd( int n, int m) { // Traverse the last row for ( int i = n - 2; i >= 0; --i) { ending[i][m - 1] += ending[i + 1][m - 1]; } // Traverse the last column for ( int i = m - 2; i >= 0; --i) { ending[n - 1][i] += ending[n - 1][i + 1]; } // Traverse the matrix for ( int i = n - 2; i >= 0; --i) { for ( int j = m - 2; j >= 0; --j) { // Update the value of // ending[i][j] ending[i][j] += max(ending[i + 1][j], ending[i][j + 1]); } } } // Function to find the maximum path sum // from the top-left to the bottom right // cell such that path contains one of // the cells in the array coordinates[][] void maximumPathSum( int mat[][3], int n, int m, int q, int coordinates[][2]) { // Initialize the start and the // end matrices for ( int i = 0; i < n; ++i) { for ( int j = 0; j < m; ++j) { start[i][j] = mat[i][j]; ending[i][j] = mat[i][j]; } } // Calculate the start matrix calculateStart(n, m); // Calculate the end matrix calculateEnd(n, m); // Stores the maximum path sum int ans = 0; // Traverse the coordinates for ( int i = 0; i < q; ++i) { int X = coordinates[i][0] - 1; int Y = coordinates[i][1] - 1; // Update the value of ans ans = max(ans, start[X][Y] + ending[X][Y] - mat[X][Y]); } // Print the resultant maximum // sum path value cout << ans; } // Drive Code int main() { int mat[][3] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int N = 3; int M = 3; int Q = 2; int coordinates[][2] = { { 1, 2 }, { 2, 2 } }; maximumPathSum(mat, N, M, Q, coordinates); } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Stores the maximum path sum from the // cell (1, 1) to (N, M) static int start[][] = new int [ 3 ][ 3 ]; // Stores the maximum path sum from the // cell (j, j) to (N, M) static int ending[][] = new int [ 3 ][ 3 ]; // Function to find the maximum path // sum from the cell (1, 1) to (N, M) static void calculateStart( int n, int m) { // Traverse the first row for ( int i = 1 ; i < m; ++i) { start[ 0 ][i] += start[ 0 ][i - 1 ]; } // Traverse the first column for ( int i = 1 ; i < n; ++i) { start[i][ 0 ] += start[i - 1 ][ 0 ]; } // Traverse the matrix for ( int i = 1 ; i < n; ++i) { for ( int j = 1 ; j < m; ++j) { // Update the value of // start[i][j] start[i][j] += Math.max(start[i - 1 ][j], start[i][j - 1 ]); } } } // Function to find the maximum path // sum from the cell (j, j) to (N, M) static void calculateEnd( int n, int m) { // Traverse the last row for ( int i = n - 2 ; i >= 0 ; --i) { ending[i][m - 1 ] += ending[i + 1 ][m - 1 ]; } // Traverse the last column for ( int i = m - 2 ; i >= 0 ; --i) { ending[n - 1 ][i] += ending[n - 1 ][i + 1 ]; } // Traverse the matrix for ( int i = n - 2 ; i >= 0 ; --i) { for ( int j = m - 2 ; j >= 0 ; --j) { // Update the value of // ending[i][j] ending[i][j] += Math.max(ending[i + 1 ][j], ending[i][j + 1 ]); } } } // Function to find the maximum path sum // from the top-left to the bottom right // cell such that path contains one of // the cells in the array coordinates[][] static void maximumPathSum( int mat[][], int n, int m, int q, int coordinates[][]) { // Initialize the start and the // end matrices for ( int i = 0 ; i < n; ++i) { for ( int j = 0 ; j < m; ++j) { start[i][j] = mat[i][j]; ending[i][j] = mat[i][j]; } } // Calculate the start matrix calculateStart(n, m); // Calculate the end matrix calculateEnd(n, m); // Stores the maximum path sum int ans = 0 ; // Traverse the coordinates for ( int i = 0 ; i < q; ++i) { int X = coordinates[i][ 0 ] - 1 ; int Y = coordinates[i][ 1 ] - 1 ; // Update the value of ans ans = Math.max(ans, start[X][Y] + ending[X][Y] - mat[X][Y]); } // Print the resultant maximum // sum path value System.out.print(ans); } // Driver Code public static void main(String[] args) { int mat[][] = { { 1 , 2 , 3 }, { 4 , 5 , 6 }, { 7 , 8 , 9 } }; int N = 3 ; int M = 3 ; int Q = 2 ; int coordinates[][] = { { 1 , 2 }, { 2 , 2 } }; maximumPathSum(mat, N, M, Q, coordinates); } } // This code is contributed by code_hunt |
Python3
# Python3 program for the above approach # Stores the maximum path sum from the # cell (1, 1) to (N, M) start = [[ 0 for i in range ( 3 )] for j in range ( 3 )] # Stores the maximum path sum from the # cell (j, j) to (N, M) ending = [[ 0 for i in range ( 3 )] for j in range ( 3 )] # Function to find the maximum path # sum from the cell (1, 1) to (N, M) def calculateStart(n, m): # Traverse the first row for i in range ( 1 , m, 1 ): start[ 0 ][i] + = start[ 0 ][i - 1 ] # Traverse the first column for i in range ( 1 , n, 1 ): start[i][ 0 ] + = start[i - 1 ][ 0 ] # Traverse the matrix for i in range ( 1 , n, 1 ): for j in range ( 1 , m, 1 ): # Update the value of # start[i][j] start[i][j] + = max (start[i - 1 ][j], start[i][j - 1 ]) # Function to find the maximum path # sum from the cell (j, j) to (N, M) def calculateEnd(n, m): # Traverse the last row i = n - 2 while (i > = 0 ): ending[i][m - 1 ] + = ending[i + 1 ][m - 1 ] i - = 1 # Traverse the last column i = m - 2 while (i > = 0 ): ending[n - 1 ][i] + = ending[n - 1 ][i + 1 ] i - = 1 # Traverse the matrix i = n - 2 while (i > = 0 ): j = m - 2 while (j > = 0 ): # Update the value of # ending[i][j] ending[i][j] + = max (ending[i + 1 ][j], ending[i][j + 1 ]) j - = 1 i - = 1 # Function to find the maximum path sum # from the top-left to the bottom right # cell such that path contains one of # the cells in the array coordinates[][] def maximumPathSum(mat, n, m, q, coordinates): # Initialize the start and the # end matrices for i in range (n): for j in range (m): start[i][j] = mat[i][j] ending[i][j] = mat[i][j] # Calculate the start matrix calculateStart(n, m) # Calculate the end matrix calculateEnd(n, m) # Stores the maximum path sum ans = 0 # Traverse the coordinates for i in range (q): X = coordinates[i][ 0 ] - 1 Y = coordinates[i][ 1 ] - 1 # Update the value of ans ans = max (ans, start[X][Y] + ending[X][Y] - mat[X][Y]) # Print the resultant maximum # sum path value print (ans) # Driver Code if __name__ = = '__main__' : mat = [ [ 1 , 2 , 3 ], [ 4 , 5 , 6 ], [ 7 , 8 , 9 ] ] N = 3 M = 3 Q = 2 coordinates = [ [ 1 , 2 ], [ 2 , 2 ] ] maximumPathSum(mat, N, M, Q,coordinates) # This code is contributed by ipg2016107 |
C#
// C# program for the above approach using System; class GFG{ // Stores the maximum path sum from the // cell (1, 1) to (N, M) static int [,] start = new int [3, 3]; // Stores the maximum path sum from the // cell (j, j) to (N, M) static int [,] ending = new int [3, 3]; // Function to find the maximum path // sum from the cell (1, 1) to (N, M) static void calculateStart( int n, int m) { // Traverse the first row for ( int i = 1; i < m; ++i) { start[0, i] += start[0, i - 1]; } // Traverse the first column for ( int i = 1; i < n; ++i) { start[i, 0] += start[i - 1, 0]; } // Traverse the matrix for ( int i = 1; i < n; ++i) { for ( int j = 1; j < m; ++j) { // Update the value of // start[i][j] start[i, j] += Math.Max(start[i - 1, j], start[i, j - 1]); } } } // Function to find the maximum path // sum from the cell (j, j) to (N, M) static void calculateEnd( int n, int m) { // Traverse the last row for ( int i = n - 2; i >= 0; --i) { ending[i, m - 1] += ending[i + 1, m - 1]; } // Traverse the last column for ( int i = m - 2; i >= 0; --i) { ending[n - 1, i] += ending[n - 1, i + 1]; } // Traverse the matrix for ( int i = n - 2; i >= 0; --i) { for ( int j = m - 2; j >= 0; --j) { // Update the value of // ending[i][j] ending[i, j] += Math.Max(ending[i + 1, j], ending[i, j + 1]); } } } // Function to find the maximum path sum // from the top-left to the bottom right // cell such that path contains one of // the cells in the array coordinates[][] static void maximumPathSum( int [,] mat, int n, int m, int q, int [,] coordinates) { // Initialize the start and the // end matrices for ( int i = 0; i < n; ++i) { for ( int j = 0; j < m; ++j) { start[i, j] = mat[i, j]; ending[i, j] = mat[i, j]; } } // Calculate the start matrix calculateStart(n, m); // Calculate the end matrix calculateEnd(n, m); // Stores the maximum path sum int ans = 0; // Traverse the coordinates for ( int i = 0; i < q; ++i) { int X = coordinates[i, 0] - 1; int Y = coordinates[i, 1] - 1; // Update the value of ans ans = Math.Max(ans, start[X, Y] + ending[X, Y] - mat[X, Y]); } // Print the resultant maximum // sum path value Console.Write(ans); } // Driver Code public static void Main() { int [,] mat = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int N = 3; int M = 3; int Q = 2; int [,] coordinates = { { 1, 2 }, { 2, 2 } }; maximumPathSum(mat, N, M, Q, coordinates); } } // This code is contributed by target_2. |
Javascript
<script> // JavaScript program for the above approach // Stores the maximum path sum from the // cell (1, 1) to (N, M) var start = Array.from(Array(3), ()=>Array(3)); // Stores the maximum path sum from the // cell (j, j) to (N, M) var ending = Array.from(Array(3), ()=>Array(3)); // Function to find the maximum path // sum from the cell (1, 1) to (N, M) function calculateStart(n, m) { // Traverse the first row for ( var i = 1; i < m; ++i) { start[0][i] += start[0][i - 1]; } // Traverse the first column for ( var i = 1; i < n; ++i) { start[i][0] += start[i - 1][0]; } // Traverse the matrix for ( var i = 1; i < n; ++i) { for ( var j = 1; j < m; ++j) { // Update the value of // start[i][j] start[i][j] += Math.max(start[i - 1][j], start[i][j - 1]); } } } // Function to find the maximum path // sum from the cell (j, j) to (N, M) function calculateEnd(n, m) { // Traverse the last row for ( var i = n - 2; i >= 0; --i) { ending[i][m - 1] += ending[i + 1][m - 1]; } // Traverse the last column for ( var i = m - 2; i >= 0; --i) { ending[n - 1][i] += ending[n - 1][i + 1]; } // Traverse the matrix for ( var i = n - 2; i >= 0; --i) { for ( var j = m - 2; j >= 0; --j) { // Update the value of // ending[i][j] ending[i][j] += Math.max(ending[i + 1][j], ending[i][j + 1]); } } } // Function to find the maximum path sum // from the top-left to the bottom right // cell such that path contains one of // the cells in the array coordinates[][] function maximumPathSum(mat, n, m, q, coordinates) { // Initialize the start and the // end matrices for ( var i = 0; i < n; ++i) { for ( var j = 0; j < m; ++j) { start[i][j] = mat[i][j]; ending[i][j] = mat[i][j]; } } // Calculate the start matrix calculateStart(n, m); // Calculate the end matrix calculateEnd(n, m); // Stores the maximum path sum var ans = 0; // Traverse the coordinates for ( var i = 0; i < q; ++i) { var X = coordinates[i][0] - 1; var Y = coordinates[i][1] - 1; // Update the value of ans ans = Math.max(ans, start[X][Y] + ending[X][Y] - mat[X][Y]); } // Print the resultant maximum // sum path value document.write( ans); } // Drive Code var mat = [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]; var N = 3; var M = 3; var Q = 2; var coordinates = [ [ 1, 2 ], [ 2, 2 ] ]; maximumPathSum(mat, N, M, Q, coordinates); </script> |
27
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!