# Maximum path sum in matrix

Given a matrix of N * M. Find the maximum path sum in matrix. The maximum path is sum of all elements from first row to last row where you are allowed to move only down or diagonally to left or right. You can start from any element in first row.

Examples:

```Input : mat[][] = 10 10  2  0 20  4
1  0  0 30  2  5
0 10  4  0  2  0
1  0  2 20  0  4
Output : 74
The maximum sum path is 20-30-4-20.

Input : mat[][] = 1 2 3
9 8 7
4 5 6
Output : 17
The maximum sum path is 3-8-6.```

We are given a matrix of N * M. To find max path sum first we have to find max value in first row of matrix. Store this value in res. Now for every element in matrix update element with max value which can be included in max path. If the value is greater then res then update res. In last return res which consists of max path sum value.

`// CPP prorgam for finding max path in matrix`
`#include <bits/stdc++.h>`
`#define N 4`
`#define M 6`
`using` `namespace` `std;`
`// To calculate max path in matrix`
`int` `findMaxPath(``int` `mat[][M])`
`{`
`    ``// To find max val in first row`
`    ``int` `res = -1;`
`    ``for` `(``int` `i = 0; i < M; i++)`
`        ``res = max(res, mat[0][i]);`
`    ``for` `(``int` `i = 1; i < N; i++) {`
`        ``res = -1;`
`        ``for` `(``int` `j = 0; j < M; j++) {`
`            ``// When all paths are possible`
`            ``if` `(j > 0 && j < M - 1)`
`                ``mat[i][j] += max(mat[i - 1][j],`
`                                 ``max(mat[i - 1][j - 1], `
`                                     ``mat[i - 1][j + 1]));`
`            ``// When diagonal right is not possible`
`            ``else` `if` `(j > 0)`
`                ``mat[i][j] += max(mat[i - 1][j],`
`                                 ``mat[i - 1][j - 1]);`
`            ``// When diagonal left is not possible`
`            ``else` `if` `(j < M - 1)`
`                ``mat[i][j] += max(mat[i - 1][j],`
`                                 ``mat[i - 1][j + 1]);`
`            ``// Store max path sum`
`            ``res = max(mat[i][j], res);`
`        ``}`
`    ``}`
`    ``return` `res;`
`}`
`// Driver program to check findMaxPath`
`int` `main()`
`{`
`    ``int` `mat[N][M] = { { 10, 10, 2, 0, 20, 4 },`
`                      ``{ 1, 0, 0, 30, 2, 5 },`
`                      ``{ 0, 10, 4, 0, 2, 0 },`
`                      ``{ 1, 0, 2, 20, 0, 4 } };`
`    ``cout << findMaxPath(mat);`
`    ``return` `0;`
`}`

Output:

```74
```

Time Complexity: O(N*M)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/maximum-path-sum-matrix/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Skip to toolbar