Maximum Path Sum in Grid

Implement maxPathSum

Given the values on a grid, and starting at the top-left corner with only right and down moves allowed, find the maximum possible sum of any path to the bottom-right corner — the total of every cell's value along the way, including both endpoints. Every cell's best total depends only on the two cells that could lead into it — the one above, or the one to its left — so working through the grid one row at a time, always keeping the bigger of those two running totals, lets every later cell be resolved using totals already computed for the cells before it. The very first row and first column each only have one possible way in along the edge, so their running totals are a plain accumulation with no comparison needed. By the time the sweep reaches the bottom-right corner, it holds the maximum total for the whole grid.

Example 1:

Input: grid = [[4,2,3],[1,6,2],[5,1,7]]

Output: 21

Example 2:

Input: grid = [[6,1],[3,9]]

Output: 18

Example 3:

Input: grid = [[5]]

Output: 5

+ 7 hidden test cases run on Submit.

Constraints:

  • 1 ≤ grid.length, grid[0].length ≤ 20
  • -100 ≤ grid[i][j] ≤ 100

grid =

[[4,2,3], [1,6,2], [5,1,7]]