Maximum Path Sum in Grid

Medium15–20 min

Topics

Dynamic ProgrammingMatrix

Companies

AmazonFlipkart

Given the values on a grid, and starting at the top-left corner with only right and down moves allowed, find the maximum possible sum of any path to the bottom-right corner — the total of every cell's value along the way, including both endpoints. Every cell's best total depends only on the two cells that could lead into it — the one above, or the one to its left — so working through the grid one row at a time, always keeping the bigger of those two running totals, lets every later cell be resolved using totals already computed for the cells before it. The very first row and first column each only have one possible way in along the edge, so their running totals are a plain accumulation with no comparison needed. By the time the sweep reaches the bottom-right corner, it holds the maximum total for the whole grid.

Test Case 1:

Input:grid = [[4,2,3],[1,6,2],[5,1,7]]

Output:21

Explanation:The path 4→1→5→1→7 (down, down, right, right — always choosing whichever move keeps the running total highest) totals 21, the largest of any right/down route.

Test Case 2:

Input:grid = [[6,1],[3,9]]

Output:18

Explanation:The path 6→3→9 (down, right) totals 18, beating 6→1→9 which totals 16.

Test Case 3:

Input:grid = [[5]]

Output:5

Explanation:A single-cell grid has only one possible path: the cell itself.

Constraints

◆1 ≤ grid.length, grid[0].length ≤ 20
◆-100 ≤ grid[i][j] ≤ 100

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Standing on any cell, the largest total reachable from there to the bottom-right corner is that cell's own value plus whichever of the two possible next moves — one step down or one step right — leads to a bigger total. Reaching the bottom-right corner costs exactly that cell's own value, since there's nowhere left to go, and stepping past the bottom or right edge simply isn't a valid move. Recursing from the top-left corner and always taking whichever next move leads to the bigger total finds the maximum path sum, though the same cell ends up recomputed every time a different path reaches it.

TimeO(2^(m+n))

SpaceO(m + n)

Java

Try it out

class Solution {
    private int[][] grid;
    private int m;
    private int n;

    public int maxPathSum(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        return solve(0, 0);
    }

    private int solve(int i, int j) {
        if (i == m - 1 && j == n - 1) return grid[i][j];
        int best = Integer.MIN_VALUE;
        if (i + 1 < m) best = Math.max(best, solve(i + 1, j));
        if (j + 1 < n) best = Math.max(best, solve(i, j + 1));
        return grid[i][j] + best;
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Track, for the row currently being processed, the biggest total reachable from the top-left corner to each column. The very first cell just takes its own value, since nothing leads into it. Every other cell in the first row can only be reached from the left, so its total simply adds this cell's value onto the running total from the previous column. Every other cell in the first column can only be reached from above, so its total adds onto whatever is already sitting at that column. Every remaining cell picks whichever of those two arrivals — from above, or from the left — is bigger, and adds its own value on top. Sweeping through every row this way, the last column ends up holding the maximum total to the bottom-right corner.

TimeO(m × n)

SpaceO(n)