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.
grid with m rows and n columns.grid[i][j] >= 0.0 means the cell cannot be used.Return a single integer: the maximum sum of gold collectable along any valid path.
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
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.