When solving gridbased problems, one common challenge is to determine the maximum sum of values starting from the topleft corner of the grid and moving to the bottomright corner. You are only allowed to move right or down. This problem can be elegantly solved using recursive depthfirst 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 topleft corner to the bottomright 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 topleft cell and ending at the bottomright cell.
Algorithm Overview
To tackle this problem, we use a recursive approach to explore all possible paths from the topleft corner to the bottomright corner. The key steps in the algorithm are:

Base Case:
 If the current position is out of bounds, return negative infinity to indicate an invalid path.
 If the current position is the bottomright corner, return the value at that cell.

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 bottomright 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
(bottomright 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 bottomright 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
:

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 bottomright corner. Return
4
.
 Reached the bottomright corner. Return
 Move Down to (1,2) again. Return
4
.
 Move Down to (1,2) with value
 Max Path Sum from (0,1):
2 + max(0 + 4, 4) = 2 + 4 = 6
 Move Right to (0,2) with value

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 bottomright corner. Return
4
.
 Reached the bottomright corner. Return
 Move Down to (2,2): Out of bounds.
 Move Right to (1,2) with value
 Max Path Sum from (1,1):
5 + max(4, ∞) = 5 + 4 = 9
 Max Path Sum from (1,0):
3 + 9 = 12
 Move Right to (1,1) with value

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 topleft corner to the bottomright 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!