Maximum Value Path in a Grid

You are given a grid of size M × N where each cell contains an integer value. A robot starts at the top-left corner (cell (0,0)) and can only move either right or down at each step. The task is to determine the maximum sum of values that the robot can collect on its journey to the bottom-right corner (cell (M-1, N-1)).

The path sum is calculated by summing the values of all cells visited along the path. Formally, if we define a dynamic programming table \(dp\) with the recurrence:

\(dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + grid[i][j]\)

with base conditions \(dp[0][0] = grid[0][0]\), and appropriate handling for the first row and first column, then your goal is to compute \(dp[M-1][N-1]\).

Note: The grid might contain negative values as well.

inputFormat

The input is read from stdin and has the following format:

• The first line contains two space-separated integers M and N, representing the number of rows and columns respectively.
• This is followed by M lines, each containing N space-separated integers representing the grid values.

outputFormat

Output a single integer to stdout representing the maximum sum of the values collected on a valid path from the top-left to the bottom-right corner.

3 3
1 -3 4
2 0 6
-1 4 3

12