Intermediate Level
Implement the maximumPathSumGrid method that finds the maximum path sum from the top-left to the bottom-right of a grid.
The input contains a matrix grid with rows rows and cols columns. Your task is to find the maximum path sum from the top-left cell to the bottom-right cell.
From each cell, you may move only right or down. Add the values of all cells included in the path. For example, in [[1,3,1],[1,5,1],[4,2,1]], the maximum path sum is 12.
Example 1
Input
grid (int[][]) =
[[1,3,1],[1,5,1],[4,2,1]]rows (int) =
3cols (int) =
3Returns (int)
12Example 2
Input
grid (int[][]) =
[[5]]rows (int) =
1cols (int) =
1Returns (int)
5Example 3
Input
grid (int[][]) =
[[1,2,3],[4,5,6]]rows (int) =
2cols (int) =
3Returns (int)
16Use dynamic programming to store the best sum that can reach each cell.
The first cell starts with its own value. For every other cell, you can come either from the top cell or from the left cell. To maximize the path sum, add the current cell value to the larger of those two previous sums.
The value stored at the bottom-right cell is the maximum path sum.
Pseudocode:
function maximumPathSumGrid(grid, rows, cols):
dp = 2D array of size rows x cols
for r from 0 to rows - 1:
for c from 0 to cols - 1:
if r == 0 and c == 0:
dp[r][c] = grid[r][c]
else:
bestPrevious = negative infinity
if r > 0:
bestPrevious = max(bestPrevious, dp[r - 1][c])
if c > 0:
bestPrevious = max(bestPrevious, dp[r][c - 1])
dp[r][c] = grid[r][c] + bestPrevious
return dp[rows - 1][cols - 1]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run