Maximum Path Sum in the matrix

Find Maximum Path sum but this time its variable starting point you can go down , downRight, downLeft

Maximum Path Sum in a Matrix

Problem Statement

You are given an N x M matrix filled with integers. Find the maximum sum of a path that starts at any cell in the first row, and ends at any cell in the last row.

From a cell (row, col), you can move to any of three cells in the row directly below:

• Down: (row + 1, col)
• Down-left diagonal: (row + 1, col - 1)
• Down-right diagonal: (row + 1, col + 1)

Constraints

• 1 ≤ T ≤ 50
• 1 ≤ N ≤ 100
• 1 ≤ M ≤ 100
• −10⁴ ≤ matrix[i][j] ≤ 10⁴

Where T is the number of test cases, N is the number of rows, M is the number of columns, and matrix[i][j] is the value at row i, column j.

Time Limit: 1 second

Examples

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:

• In the first test case, the maximum path sum is 2 → 100 → 1 → 2, giving a total of 105 (2 + 100 + 1 + 2).
• In the second test case, the maximum path sum is 10 → 7 → 8, giving a total of 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:

• In the first test case, the maximum path sum is 3 → 8 → 6, giving a total of 17 (3 + 8 + 6).
• In the second test case, the maximum path sum is 20 → 30 → 4 → 20, giving a total of 74 (20 + 30 + 4 + 20).

Solution

This is a variation of a standard matrix path problem, where the path can start from any column in the first row (instead of being fixed to a specific starting cell).

Brute Force

For each cell, we try all three possible moves to the row below (down, down-left, down-right), and take whichever gives the largest total. We try this starting from every column in the first row, and return the best overall result.

maximumPath(mat) {
    let m = mat.length;
    let n = mat[0].length;

    function recurr(i, j) {
        if (j >= n || j < 0) {
            return -Infinity;
        }

        if (i == m - 1) {
            return mat[i][j];
        }

        let upLeft = recurr(i + 1, j - 1);
        let up = recurr(i + 1, j);
        let upRight = recurr(i + 1, j + 1);

        let max = Math.max(upLeft, up, upRight);

        return max + mat[i][j];
    }

    let maximum = 0;

    for (let col = 0; col < n; col++) {
        maximum = Math.max(recurr(0, col), maximum);
    }

    return maximum;
}

Memoization (Top-Down)

We use the same recursive approach, but store each cell's result in a dp grid the first time we calculate it, so we don't repeat the same work.

maximumPath(mat) {
    let m = mat.length;
    let n = mat[0].length;
    let dp = Array.from({ length: m }, () => Array(n));

    function recurr(i, j, dp) {
        if (j >= n || j < 0) {
            return -Infinity;
        }

        if (i == m - 1) {
            return mat[i][j];
        }

        if (dp[i][j] !== undefined) {
            return dp[i][j];
        }

        let upLeft = recurr(i + 1, j - 1, dp);
        let up = recurr(i + 1, j, dp);
        let upRight = recurr(i + 1, j + 1, dp);

        let max = Math.max(upLeft, up, upRight);
        dp[i][j] = max + mat[i][j];
        return dp[i][j];
    }

    let maximum = 0;

    for (let col = 0; col < n; col++) {
        maximum = Math.max(recurr(0, col, dp), maximum);
    }

    return maximum;
}

Tabulation (Bottom-Up)

Instead of starting from the top and recursing downward, we start from the last row (where the answer for each cell is just its own value), and work our way upward, filling in each row based on the row below it.

maximumPath(mat) {
    let m = mat.length;
    let n = mat[0].length;
    let dp = Array.from({ length: m }, () => Array(n));

    for (let col = 0; col < n; col++) {
        dp[m - 1][col] = mat[m - 1][col];
    }

    for (let i = m - 2; i >= 0; i--) {
        for (let j = 0; j < n; j++) {

            let down = dp[i + 1][j];
            let downLeft = 0;
            if (j > 0)
                downLeft = dp[i + 1][j - 1];

            let downRight = 0;
            if (j < n - 1)
                downRight = dp[i + 1][j + 1];

            let max = Math.max(down, downLeft, downRight);

            dp[i][j] = mat[i][j] + max;
        }
    }

    return Math.max(...dp[0]);
}