Path with Maximum Gold

Choose a starting cell containing gold in grid, then follow a path through cells sharing an edge: up, down, left, or right. Each positive entry is the amount of gold collected when visiting that cell; zero marks a cell you cannot enter. You may not visit any cell twice. You may stop anywhere. Return the maximum gold obtainable along one path, or 0 if no cell contains gold.

Example 1:

Input: grid = [[2,3,4]]

Output: 9

Explanation: Start at either end and visit all three cells in order. The total is 2 + 3 + 4 = 9.

Example 2:

Input: grid = [[5,0,9]]

Output: 9

Explanation: The zero cell separates the two gold cells and cannot be entered. Starting and stopping at the cell containing 9 gives the maximum.

Example 3:

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

Output: 15

Explanation: Follow the values 5, 4, 6 for a total of 15. A path cannot collect a third arm of the cross because doing so would revisit the center cell.

Constraints:

• 1 <= grid.length <= 15
• Every row has the same length, between 1 and 15.
• 0 <= grid[i][j] <= 100
• At most 25 cells have positive values.