Close
Topic list
Maximum Path Sum in the matrix
MEDIUM
35 mins
Matrices (2D Arrays)
Dynamic Programming
Topics (Covered in this problem)
Problem solved
Skill meter
Matrices (2D Arrays)
-
Dynamic Programming
-
Other topics
Problem solved
Skill meter
Strings
-
Sorting
-
Binary Search
-
-
Stacks & Queues
-
Trees
-
Graph
-
Greedy
-
Tries
-
Arrays
-
Binary Search Trees
-
Heap
-
Bit Manipulation
-

# Maximum Path Sum in the matrix

Contributed by
Pankaj Sharma
Medium
Avg time to solve 35 mins
Success Rate 70 %
Share

## Problem Statement

#### From a cell in a row, you can move to another cell directly below that row, or diagonally below left or right. So from a particular cell (row, col), we can move in three directions i.e.

``````Down: (row+1,col)
Down left diagonal: (row+1,col-1)
Down right diagonal: (row+1, col+1)
``````
Detailed explanation ( Input/output format, Notes, Constraints, Images )
##### Input 1 :
``````2
4 4
1 2 10 4
100 3 2 1
1 1 20 2
1 2 2 1
3 3
10 2 3
3 7 2
8 1 5
``````
##### Output 1 :
``````105
25
``````
##### Explanation Of Input 1 :
``````In the first test case for the given matrix,
``````

``````The maximum path sum will be 2->100->1->2, So the sum is 105(2+100+1+2).

In the second test case for the given matrix, the maximum path sum will be 10->7->8, So the sum is 25(10+7+8).
``````
##### Input 2 :
``````2
3 3
1 2 3
9 8 7
4 5 6
4 6
10 10 2 -13 20 4
1 -9 -81 30 2 5
0 10 4 -79 2 -10
1 -5 2 20 -11 4
``````
##### Output 2 :
``````17
74
``````
##### Explanation Of Input 2 :
``````In the first test case for the given matrix, the maximum path sum will be 3->8->6, So the sum is 17(3+8+6).

In the second test case for the given matrix, the maximum path sum will be 20->30->4->20, So the sum is 74(20+30+4+20).
``````
Console