该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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.

Solutie

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)