Given a grid of integers, return the maximum sum collectable on a path from the top-left to the bottom-right cell, moving only right or down.
maxPathSum(grid)
Input format: rows separated by ;, values space-separated. For example
1 2 3;4 5 6.
[[1,2,3],[4,5,6]] // → 16 (1→4→5→6)
[[5]] // → 5
[[1,2],[1,1]] // → 4 (1→2→1)
The counting-paths idea with a twist: instead of counting right/down paths, find the one whose values sum highest. At any cell, the best total from here is this cell's value plus whichever of "best going right" or "best going down" is larger.
At the destination, the best total is just the cell's own value. Stepping off the grid is invalid — represent it as an extremely negative value so it's never chosen over a real path.
Many routes converge on the same cell — right-then-down and down-then-right both reach the same intermediate cell. The naive recursion recomputes the best onward sum from that cell for every route that reaches it, even though it's a fixed quantity depending only on position. This grows exponentially with grid size.
The best sum from a cell to the destination depends only on (row, column). Cache keyed by (row, column); check before recursing, otherwise compute the cell's value plus the better neighbor result, store, return.
Only rows × cols distinct cells exist, each computed once at constant cost — O(rows × cols) instead of exponential.
def max_path_sum(grid):
rows = len(grid)
cols = len(grid[0])
NEG = float("-inf")
memo = {}
def best(r, c):
if r >= rows or c >= cols:
return NEG
if r == rows - 1 and c == cols - 1:
return grid[r][c]
key = (r, c)
if key in memo:
return memo[key]
v = grid[r][c] + max(best(r + 1, c), best(r, c + 1))
memo[key] = v
return v
return best(0, 0)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.