Matrix Max Sum Path Problem in Java

It is a problem frequently asked in interviews of top IT companies like Google, Amazon, TCS, Accenture, etc. By solving the problem, one wants to check the logical ability, critical thinking, and problem-solving skill of the interviewee. So, in this section, we are going to solve matrix max sum path problem with different approaches and logic. Also, we will create Java programs for the same.

Problem Statement

We have given a matrix of n×m. In this matrix, we have to find the max path sum first. The movement in matrix is allowed form the top-left corner to the bottom-right corner. The movement direction must be right, downwards, or diagonally right (from (i, j) to (i+1, j), (i, j+1), or (i+1, j+1)).

Solution to the Problem

To find the max path sum first, we have to find the max value in the first row of the matrix. Store this value in res variable. Now for every element in the matrix update element with max value that can be included in max path. If the value is greater then res variable, then update the res variable. At last return res variable that consists of max path sum value.

Let's understand it through an example.

Matrix Max Sum Path Example

Input Matrix:

Output:

 500 

Explanation:

Example 2:

Input Matrix:

Output:

 3000 

Explanation:

Example 3:

Input Matrix:

Output:

 2300 

Explanation:

We can solve the above problem by using the following three approaches.

• Using Recursion
• Using Dynamic Programming
• Using Tabulation

Approach: Using Recursion

The naive approach using recursion for the Matrix Max Sum Path Problem involves recursively exploring all possible paths from the top to the bottom of a matrix, calculating the maximum sum path without utilizing memoization to store computed results.

Algorithm:

Step 1: Define a MatrixMaxSumPathNaive class with a main method to initialize a sample integer matrix.

Step 2: Create a method maxSumPath that takes a 2D integer array matrix as input. Determine the number of rows rows and columns cols in the matrix. Begin recursion by calling maxSumPathRecursive(matrix, 0, 0, rows, cols).

Step 3: Define a private static method maxSumPathRecursive to recursively find the maximum sum path. Parameters include matrix, current row, current col, total rows, and total cols.

• Base Case: Return matrix[row][col] if row equals rows - 1, indicating the bottom-most row.
• Initialization: Start maxPathSum at Integer.MIN_VALUE.

Step 4: Calculate maximum path sum by:

• Moving downward: matrix[row][col] + maxSumPathRecursive(matrix, row + 1, col, rows, cols).
• Moving downward-left (if col > 0): matrix[row][col] + maxSumPathRecursive(matrix, row + 1, col - 1, rows, cols).
• Moving downward-right (if col < cols - 1): matrix[row][col] + maxSumPathRecursive(matrix, row + 1, col + 1, rows, cols).

Step 5: Return maxPathSum, the maximum sum path found from the current cell.

Step 6: After calling maxSumPath(matrix) in main, print the result to show the maximum sum path found in the matrix using the naive recursive approach.

Let's implement the above steps in a Java program.

Implementation of Matrix Max Path Sum Problem Using Recursion

File Name: MatrixMaxSumPathNaive.java

Output:

 Maximum sum path in the matrix (naive approach): 17 

Time Complexity: The time complexity of the naive recursive approach is O(3^{n}), where n is the number of rows in the matrix. It is because, from each cell, the function can move in three possible directions (down, down-left, down-right), leading to an exponential number of recursive calls.

Auxiliary Space: The auxiliary space is O(n), where n is the number of rows. The space is used by the recursion stack, with the maximum depth of recursion being equal to the number of rows in the worst case.

Approach: Dynamic Programming

Dynamic programming is a problem-solving technique where solutions to subproblems are stored and reused to efficiently solve larger instances of the problem. It optimally solves complex problems by breaking them down into simpler overlapping subproblems, often using a table (memoization) or bottom-up approach to build solutions iteratively.

Algorithm:

Step 1: Define MAX_SIZE for the maximum size of the matrix and declare numRows, numCols, matrix, dp, and visited arrays.

Step 2: Implement inputMatrix() to set numRows, numCols, and populate matrix with values.

Step 3: Define maximumSumPath(int row, int col) to compute the maximum sum path from cell (row, col).

Step 4: If at bottom-right corner, return its value. If cell is visited, return stored value from dp. Mark as Visited and Set visited[row][col] to 1.

Step 5: Initialize totalSum. If not on the last row or column, calculate the maximum sum from moving right, diagonally down-right, or down.

• If on the last row, only move right.
• If on the last column, only move down.
• Add current cell's value to the maximum of the sums obtained.
• Update dp[row][col] with totalSum.

Step 6: Return the updated maximum sum value for the current cell.

Step 7: Call inputMatrix(). Call maximumSumPath(0, 0) to find the maximum sum path from the top-left corner and print the result.

Let's implement the above steps in a Java program.

Implementation of Matrix Max Path Sum Problem Using Dynamic Programming

File Name: MatrixMaxSumPath.java

Output:

 Maximum sum path in the matrix: 29 

Time Complexity: The time complexity is O(n×m), as each cell is processed at most once due to memoization.

Auxiliary Space: The auxiliary space is O(n×m), for the dp and visited arrays.

Approach: Using Tabulation

In this approach, a dynamic programming (DP) table is used to iteratively compute the maximum sum path from the bottom-right corner to the top-left corner of the matrix. The bottom-up method avoids redundant calculations and ensures optimal substructure by building the solution incrementally.

Algorithm:

Step 1: Define a function maxSumPath(int[][] matrix) to find the maximum sum path in a given matrix.

Step 2: Initialize variables rows and cols to store the number of rows and columns in matrix and create a 2D array dp of size rows x cols to store the maximum sums.

Step 3: Set dp[rows - 1][cols - 1] to matrix[rows - 1][cols - 1], representing the bottom-right corner of the matrix.

Step 4: Iterate over the last row and column of dp to calculate maximum sums:

• For the last row (i = rows - 2 to 0): dp[i][cols - 1] = matrix[i][cols - 1] + dp[i + 1][cols - 1].
• For the last column (j = cols - 2 to 0): dp[rows - 1][j] = matrix[rows - 1][j] + dp[rows - 1][j + 1].

Step 5: Iterate through the rest of the dp table from bottom-right to top-left (i = rows - 2 to 0, j = cols - 2 to 0):

• Calculate each dp[i][j] as matrix[i][j] + max(dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1]), ensuring to stay within matrix bounds.

Step 6: The maximum sum path from the top-left corner of the matrix is stored in dp[0][0].

Let's implement the above steps in a Java program.

Implementation of Matrix Max Path Sum Problem Using Tabulation

File Name: MatrixMaxSumPathTabulation.java

Output:

 Maximum sum path in the matrix (tabulation approach): 35 

Time Complexity: The time complexity of the provided code is O(n×m), where n is the number of rows and m is the number of columns in the matrix. It is because each cell in the matrix is processed exactly once.

Auxiliary Space: The auxiliary space of the provided code is O(n×m), where n is the number of rows and m is the number of columns in the matrix. It is due to the additional space required for the dynamic programming table (dp) of size n×m.