128. Max Path Sum in Matrix
Max Path Sum in Matrix
You are traveling from Washington to Florida through a grid of cities. Each string in the input list represents one row of the matrix, with integer values separated by commas. Each cell in the matrix represents the number of National Parks you can visit in that city.
You start at the top-left cell and want to reach the bottom-right cell.
You may move only:
1. right
2. down
Your goal is to find the maximum total number of National Parks you can visit, along a valid path.
Return the maximum path sum from the top-left cell to the bottom-right cell.
Method Signature
int maxPathSum(List<String> matrix)
matrix is a non-empty 1-D list of strings.- Convert
matrix to a non-empty 2-D list of integers 'grid' after parsing each row string.
- Each string represents one row of the 'grid'.
- Values inside a row are separated by commas.
grid.get(0).get(0) is the starting cell after parsing.grid.get(rows - 1).get(cols - 1) is the destination cell after parsing.- From any cell, you may move only to the cell directly right or directly down.
- Return the maximum possible sum among all valid paths.
Input
matrix - a 1-D list of strings where each string represents one row of integers separated by commas.
Output
- Return an
int representing the maximum path sum from the top-left cell to the bottom-right cell.
Constraints
1 ≤ matrix.size() ≤ 200- Each row string contains between
1 and 200 integers.
- All rows contain the same number of integer values.
- There are no negative values in the matrix.
0 ≤ cell value ≤ 10^4
Examples
Example 1
maxPathSum(matrix = ["5,3,2", "1,9,1", "0,2,7"])
Output: 26
Explanation: One maximum-sum path is: 5 -> 3 -> 9 -> 2 -> 7.
Sum = 5 + 3 + 9 + 2 + 7 = 26.
Example 2
maxPathSum(matrix = ["1,2,3", "4,5,6"])
Output: 16
Explanation: One maximum-sum path is: 1 -> 4 -> 5 -> 6.
Sum = 1 + 4 + 5 + 6 = 16.
Example 3
maxPathSum(matrix = ["7"])
Output: 7
Explanation: There is only one cell, so the answer is that cell's value.
Example 4
maxPathSum(matrix = ["1,2,3", "4,5,6", "7,8,9"])
Output: 29
Explanation: One maximum-sum path is: 1 -> 4 -> 7 -> 8 -> 9.
Sum = 1 + 4 + 7 + 8 + 9 = 29.