Find the maximum amount of gold collectable by walking through a grid without revisiting cells in a path.
You are given an grid of non-negative integers. Each cell contains either no gold (0) or some positive amount of gold.
You may start from any cell that contains gold. From a cell, you can move one step up, down, left, or right. You cannot leave the grid, step onto a cell containing 0, or visit the same cell more than once in the same path.
Collect the gold from every cell you visit in a path. Your task is to return the maximum total amount of gold you can collect from any valid path.
This is a path-search problem where the key challenge is exploring all valid routes while preventing revisits.
Input Format
- The input is a 2D integer grid
gridwithmrows andncolumns. grid[i][j] >= 0.0means the cell cannot be used.- Positive values represent gold that can be collected when the cell is visited.
Output Format
Return a single integer: the maximum sum of gold collectable along any valid path.
Constraints
- is a reasonable interview-scale bound.
- Values are non-negative integers.
- A cell can be visited at most once per path.
- Movement is allowed only in the four cardinal directions.
Note: exact platform constraints may vary; this version is stated in interview-prep form.
Example 1
Input
grid = [[0,6,0],[5,8,7],[0,9,0]]
Output
24
Explanation
One optimal path is 9 -> 8 -> 7, collecting 24 gold.
Example 2
Input
grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output
28
Explanation
One optimal path is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7, collecting 28 gold.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.