Maximum Falling Path Sum
MediumP3Coding
grid has h rows and w columns of integers. You start on any cell in the first row. From a cell in row r you move to row r + 1, landing on the cell directly below or on a cell diagonally below (one column to the left or right), as long as it exists. You collect the value of every cell you visit.
Return the largest total you can collect from the first row to the last row.
Example 1
- Input
- grid = [[1,2,3],[4,5,6],[7,8,9]]
- Output
- 18
- Why
- 3 + 6 + 9 = 18 is the best path.
Example 2
- Input
- grid = [[5]]
- Output
- 5
Example 3
- Input
- grid = [[1,2,3]]
- Output
- 3
Constraints
- 1 <= h, w <= 200
- -100 <= grid[r][c] <= 100
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 9. ⌘Enter runs, ⌘⇧Enter submits.