Given a grid of stone values, find the maximum total number of stones that can be collected while moving from the bottom-left cell to the top-right cell.
The input is provided as a flattened 2-D structure:
- locations is a List<String>
- each string represents one row of the grid
- values inside a row are comma-separated integers
You start at (rows - 1, 0) and must reach (0, cols - 1).
From any cell, you may move only:
- one cell up
- one cell right
Every time you visit a cell, you collect the value stored in that cell, including the starting cell and the ending cell.
Return the maximum total value that can be collected along any valid path.
Method Signature
int maximumStones(List<String> locations)
- 1 ≤ locations.size()
- each element of locations is one row encoded as comma-separated integers
- all rows contain the same number of values
- start cell is (rows - 1, 0)
- end cell is (0, cols - 1)
- allowed moves are only up and right
Input Format
locations[i] contains the column values of row i separated by commas.
Example:
locations = ["9,0,2,0,1", "0,1,1,1,0", "2,0,0,0,0"]
Output Format
Return a single integer representing the maximum stones collectible from the bottom-left cell to the top-right cell.
Constraints
- 1 ≤ rows ≤ 1000
- 1 ≤ cols ≤ 1000
- 0 ≤ cellValue ≤ 10^6
- each row string is non-empty and contains exactly cols comma-separated integers
- the grid is rectangular
Notes
- The value of every visited cell is included in the total.
- The starting and ending cells are always part of the path.
- Because movement is restricted to only up and right, every valid path has exactly (rows - 1) + (cols - 1) moves.
Examples
Example 1:
Method call:
maximumStones(locations = ["9,0,2,0,1", "0,1,1,1,0", "2,0,0,0,0"])
Output:
14
Explanation:
One optimal path is:
(2,0) -> (1,0) -> (0,0) -> (0,1) -> (0,2) -> (0,3) -> (0,4)
Values collected:
2 + 0 + 9 + 0 + 2 + 0 + 1 = 14
Example 2:
Method call:
maximumStones(locations = ["5,1,4", "2,10,1", "3,2,8"])
Output:
20
Explanation:
One optimal path is:
(2,0) -> (1,0) -> (1,1) -> (1,2) -> (0,2)
Values collected:
3 + 2 + 10 + 1 + 4 = 20
Example 3:
Method call:
maximumStones(locations = ["7"])
Output:
7
Explanation:
The grid contains only one cell, so the start and end are the same cell.