Maximum Path Sum in a Matrix

Given an N*M matrix filled with integer numbers, determine the maximum sum that can be obtained from a path starting from any cell in the first row to any cell in the last row.

You can move from a cell in the current row to another cell directly below, or diagonally below left or right.

Input:

The first line contains an integer 'T', the number of test cases. For each test case:
The first line contains two integers 'N' and 'M', representing the matrix dimensions.
The next 'N' lines contain 'M' space-separated integers representing the matrix elements.

Output:

For each test case, print the maximum sum that can be obtained by following a path as described. Output a separate line for each test case.

Example:

Input:
2
2 3
1 2 3
4 5 6
2 2
9 10
-1 -2

Output:
11
10

Constraints:

  • 1 <= T <= 50
  • 1 <= N <= 100
  • 1 <= M <= 100
  • -104 <= matrix[i][j] <= 104
  • Time Limit: 1 second

Note:

You do not need to print anything. It has already been taken care of.
AnswerBot
4d

Find the maximum sum that can be obtained from a path in a matrix from the first row to the last row.

  • Use dynamic programming to keep track of the maximum sum at each cell in the matrix.

  • Start from the ...read more

Help your peers!
Add answer anonymously...
PayPal Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter