Matrix Maximum Path Sum Problem

Given an N*M matrix filled with integer numbers, your task is to find the maximum path sum starting from any cell in the first row and ending at any cell in the last row. You can move downward, diagonally down to the left, or diagonally down to the right from any cell.

Example:

Input:

T = 1
N = 3, M = 3
Matrix: [[3, 2, 1], [5, 10, 7], [9, 6, 8]]

Output:

18

Explanation:

The path with the maximum sum is 3 - 10 - 9, which results in a sum of 18.

Constraints:

1 ≤ T ≤ 50

1 ≤ N ≤ 100

1 ≤ M ≤ 100

-10^4 ≤ matrix[i][j] ≤ 10^4

Input:

The input will follow this format:

```
T
N M
Matrix rows
```

Output:

For each test case, you should output the maximum sum obtainable on a new line.

Note:

You are not required to print anything. The code should simply return the result.

Question

Matrix Maximum Path Sum Problem

Given an N*M matrix filled with integer numbers, your task is to find the maximum path sum starting from any cell in the first row and ending at any cell in the last row. You can move downward, diagonally down to the left, or diagonally down to the right from any cell.

Example:

Input:

T = 1
N = 3, M = 3
Matrix: [[3, 2, 1], [5, 10, 7], [9, 6, 8]]

Output:

Explanation:

The path with the maximum sum is 3 -> 10 -> 9, which results in a sum of 18.

Constraints:

1 ≤ T ≤ 50
1 ≤ N ≤ 100
1 ≤ M ≤ 100
-10^4 ≤ matrix[i][j] ≤ 10^4

Input:

The input will follow this format:

```
T
N M
Matrix rows
```

Output:

For each test case, you should output the maximum sum obtainable on a new line.

Note:

You are not required to print anything. The code should simply return the result.

Accepted Answer

Find the maximum path sum in a matrix from the first to the last row with specific movement rules.

Use dynamic programming to store maximum sums at each cell.
Start from the first row and iterate downwards.
For each cell, consider the maximum sum from the cell above, the cell diagonally left above, and the cell diagonally right above.
Update the current cell's value with the maximum path sum leading to it.
The result will be the maximum value in the last row.