Maximum sum path in a matrix from top-left to bottom-right

When solving grid-based problems, one common challenge is to determine the maximum sum of values starting from the top-left corner of the grid and moving to the bottom-right corner. You are only allowed to move right or down. This problem can be elegantly solved using recursive depth-first search (DFS) algorithms. In this blog post, we will dive into a detailed explanation of this problem and provide solutions in both Python and JavaScript.

Problem Description

Given a 2D grid of integers, our task is to find the maximum path sum from the top-left corner to the bottom-right corner. The only permissible moves are to the right and downward.

Example Grid:

[
    [1, 2, 0],
    [3, 5, 4]
]

The goal is to find the path with the highest sum, starting from the top-left cell and ending at the bottom-right cell.

Algorithm Overview

To tackle this problem, we use a recursive approach to explore all possible paths from the top-left corner to the bottom-right corner. The key steps in the algorithm are:

1. Base Case:

   • If the current position is out of bounds, return negative infinity to indicate an invalid path.
   • If the current position is the bottom-right corner, return the value at that cell.

2. Recursive Case:

   • Recursively compute the maximum path sum for the cells to the right and below the current cell.
   • Return the current cell value plus the maximum of the path sums obtained from the right and down cells.

Python Implementation

Here’s how you can implement this algorithm in Python:

def maxPathSum(grid, x=0, y=0):
    # Base case: Out of bounds
    if x >= len(grid) or y >= len(grid[0]):
        return float('-inf')
    
    # Base case: Reached the bottom-right corner
    if x == len(grid) - 1 and y == len(grid[0]) - 1:
        return grid[x][y]
    
    # Explore right and down paths
    right = maxPathSum(grid, x, y + 1)
    down = maxPathSum(grid, x + 1, y)
    
    # Return the current cell value plus the maximum path sum of right and down
    return grid[x][y] + max(right, down)

# Example usage:
grid = [
    [1, 2, 0],
    [3, 5, 4]
]
print(maxPathSum(grid))  # Output will be the maximum path sum` 

Explanation of the Code:

• maxPathSum is a recursive function that explores the grid from the starting cell (x, y).
• If out of bounds, it returns negative infinity.
• If at the destination cell (bottom-right corner), it returns the value at that cell.
• It calculates the maximum path sum by recursively moving right and down, and returns the maximum value.

JavaScript Implementation

Here is the equivalent algorithm implemented in JavaScript:

function maxPathSum(grid, x = 0, y = 0) {
    // Base case: Out of bounds
    if (x >= grid.length || y >= grid[0].length) {
        return -Infinity;
    }
    
    // Base case: Reached the bottom-right corner
    if (x === grid.length - 1 && y === grid[0].length - 1) {
        return grid[x][y];
    }
    
    // Explore right and down paths
    const right = maxPathSum(grid, x, y + 1);
    const down = maxPathSum(grid, x + 1, y);
    
    // Return the current cell value plus the maximum path sum of right and down
    return grid[x][y] + Math.max(right, down);
}

// Example usage:
const grid = [
    [1, 2, 0],
    [3, 5, 4]
];
console.log(maxPathSum(grid));  // Output will be the maximum path sum

Explanation of the Code:

• maxPathSum is a recursive function that works similarly to the Python version.
• It checks if the current position is out of bounds or if it’s at the destination cell.
• It recursively calculates the maximum path sum by exploring right and down movements, and returns the maximum value.

Detailed Example

Let’s trace the function call for the grid:

csharp

Copy code

[ [1, 2, 0], [3, 5, 4] ]

Starting at (0,0) with value 1:

1. Move Right to (0,1) with value 2:

   • Move Right to (0,2) with value 0:
     • Move Down to (1,2) with value 4:
       • Reached the bottom-right corner. Return 4.
     • Move Down to (1,2) again. Return 4.
   • Max Path Sum from (0,1): 2 + max(0 + 4, 4) = 2 + 4 = 6

2. Move Down to (1,0) with value 3:

   • Move Right to (1,1) with value 5:
     • Move Right to (1,2) with value 4:
       • Reached the bottom-right corner. Return 4.
     • Move Down to (2,2): Out of bounds.
   • Max Path Sum from (1,1): 5 + max(4, -∞) = 5 + 4 = 9
   • Max Path Sum from (1,0): 3 + 9 = 12

3. Max Path Sum from (0,0): 1 + max(6, 12) = 1 + 12 = 13

The maximum path sum is 13, which is the optimal path sum from the top-left corner to the bottom-right corner.

Conclusion

Finding the maximum path sum in a grid using recursive DFS is an effective approach. By exploring all possible paths and selecting the maximum path sum, you can solve this problem efficiently. The provided Python and JavaScript implementations showcase how to achieve this with clear and concise code. Experiment with different grids to see how the algorithm performs in various scenarios!