Problem Description

You have an m x n matrix filled with positive integers. You can move from any cell to another cell that is either below it or to its right (the cells don't need to be adjacent - you can jump to any cell in those directions).

When you move from a cell with value c1 to a cell with value c2, you gain a score of c2 - c1.

The rules are:

• You can start at any cell in the matrix
• You must make at least one move
• Each move must be either downward or rightward (to any cell in those directions, not just adjacent ones)

Your goal is to find the maximum total score you can achieve.

For example, if you move through cells with values c1 → c2 → c3, your total score would be (c2 - c1) + (c3 - c2) = c3 - c1.

The key insight is that for any path from cell with value c1 to cell with value ck, the total score simplifies to ck - c1 (the final value minus the starting value), regardless of intermediate cells visited.

The solution uses dynamic programming where f[i][j] tracks the minimum value that can reach position (i, j). For each cell, we calculate the maximum score by taking the current cell's value minus the minimum value that could have reached it from above or from the left. The answer is the maximum score across all possible endpoints.

Intuition

When we trace through any path in the matrix, let's say we move through cells with values c1 → c2 → c3 → ... → ck. The total score becomes: (c2 - c1) + (c3 - c2) + ... + (ck - ck-1)

Notice that this telescopes! All intermediate terms cancel out, leaving us with just ck - c1. This means our total score for any path depends only on the starting and ending values, not on the intermediate cells we visit.

This observation transforms our problem: instead of tracking entire paths, we only need to know:

1. What is the ending cell value? (this is given by grid[i][j])
2. What is the smallest possible starting value that can reach this ending cell?

If we can find the minimum starting value that can reach each cell (i, j), then the maximum score achievable when ending at that cell is simply grid[i][j] - minimum_starting_value.

To find the minimum starting value that can reach cell (i, j), we need to consider:

• All cells that can reach (i, j) from above (any cell in the same column with row < i)
• All cells that can reach (i, j) from the left (any cell in the same row with column < j)

But we don't need to check all these cells individually! We can use dynamic programming. If we already know the minimum value that can reach cell (i-1, j) and cell (i, j-1), then the minimum value that can reach (i, j) is either:

• The minimum value that could reach (i-1, j) (inherited from above)
• The minimum value that could reach (i, j-1) (inherited from the left)
• The value at (i, j) itself (if we start here)

This leads to our DP formulation where f[i][j] = min(f[i-1][j], f[i][j-1], grid[i][j]), and for each cell, we calculate the maximum possible score as grid[i][j] - min(f[i-1][j], f[i][j-1]).

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the solution using dynamic programming with a 2D array f where f[i][j] represents the minimum value that can reach position (i, j).

Initialization:

• Create a 2D array f with the same dimensions as the input grid
• Initialize ans = -inf to track the maximum score

Main Algorithm:

For each cell (i, j) in the grid, we perform the following steps:

1. Find the minimum value that can reach this cell from above or left:

   mi = inf
   if i > 0:
       mi = min(mi, f[i-1][j])  # minimum from above
   if j > 0:
       mi = min(mi, f[i][j-1])  # minimum from left

2. Calculate the maximum score when ending at this cell:

   ans = max(ans, x - mi)

   where x is grid[i][j]. This represents the score we get by moving from the minimum starting value to the current cell.

3. Update the DP table:

   f[i][j] = min(x, mi)

   This stores the minimum value that can reach position (i, j), which is either:

   • The current cell value x (if we start here)
   • The minimum value mi that could reach here from above or left

Key Implementation Details:

• We iterate through the grid row by row, left to right
• For the first row and first column, mi will remain as inf if there's no cell above or to the left
• The score x - mi represents moving from a cell with value mi to a cell with value x
• We continuously update ans with the maximum score found so far

Time Complexity: O(m × n) where m and n are the dimensions of the grid, as we visit each cell once.

Space Complexity: O(m × n) for the DP table f.

The beauty of this approach is that it efficiently tracks the minimum reachable value for each position while simultaneously calculating the maximum possible score, all in a single pass through the grid.

Example Walkthrough

Let's walk through a small example with a 3×3 matrix:

grid = [[1, 4, 3],
        [2, 5, 6],
        [7, 8, 9]]

We'll build our DP table f[i][j] that tracks the minimum value that can reach each position, and calculate the maximum score along the way.

Step-by-step process:

Position (0,0): value = 1

• No cells above or left, so mi = inf
• Score: 1 - inf = not valid (no previous cell)
• f[0][0] = min(1, inf) = 1

Position (0,1): value = 4

• Can only come from left: mi = f[0][0] = 1
• Score: 4 - 1 = 3
• f[0][1] = min(4, 1) = 1
• Update ans = 3

Position (0,2): value = 3

• Can only come from left: mi = f[0][1] = 1
• Score: 3 - 1 = 2
• f[0][2] = min(3, 1) = 1
• ans remains 3

Position (1,0): value = 2

• Can only come from above: mi = f[0][0] = 1
• Score: 2 - 1 = 1
• f[1][0] = min(2, 1) = 1
• ans remains 3

Position (1,1): value = 5

• From above: f[0][1] = 1
• From left: f[1][0] = 1
• mi = min(1, 1) = 1
• Score: 5 - 1 = 4
• f[1][1] = min(5, 1) = 1
• Update ans = 4

Position (1,2): value = 6

• From above: f[0][2] = 1
• From left: f[1][1] = 1
• mi = min(1, 1) = 1
• Score: 6 - 1 = 5
• f[1][2] = min(6, 1) = 1
• Update ans = 5

Position (2,0): value = 7

• Can only come from above: mi = f[1][0] = 1
• Score: 7 - 1 = 6
• f[2][0] = min(7, 1) = 1
• Update ans = 6

Position (2,1): value = 8

• From above: f[1][1] = 1
• From left: f[2][0] = 1
• mi = min(1, 1) = 1
• Score: 8 - 1 = 7
• f[2][1] = min(8, 1) = 1
• Update ans = 7

Position (2,2): value = 9

• From above: f[1][2] = 1
• From left: f[2][1] = 1
• mi = min(1, 1) = 1
• Score: 9 - 1 = 8
• f[2][2] = min(9, 1) = 1
• Update ans = 8

Final DP table f:

[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]

Maximum score: 8

This occurs when starting at cell (0,0) with value 1 and ending at cell (2,2) with value 9, giving us a score of 9 - 1 = 8. Note that the path taken doesn't matter - whether we go (0,0) → (0,1) → (2,2) or (0,0) → (1,0) → (2,2), the total score is always 8 because it only depends on the ending value minus the starting value.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the number of rows and n is the number of columns in the grid. This is because the algorithm uses two nested loops that iterate through each element of the grid exactly once. The outer loop runs m times (for each row), and the inner loop runs n times (for each column in a row), resulting in m × n total iterations. Each operation inside the loops (comparisons, min/max calculations, and assignments) takes constant time O(1).

The space complexity is O(m × n), where m is the number of rows and n is the number of columns in the grid. This is due to the creation of the 2D array f with dimensions m × n that stores intermediate values. The array f = [[0] * len(grid[0]) for _ in range(len(grid))] creates a matrix of the same size as the input grid. The remaining variables (ans, mi, i, j, x) use only constant extra space O(1), so the overall space complexity is dominated by the f matrix.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the First Cell Special Case

A critical pitfall is not properly handling when i = 0 and j = 0 (the top-left cell). At this position, there are no cells above or to the left, so min_previous remains as inf. This leads to calculating grid[0][0] - inf = -inf for the score, which incorrectly influences the maximum score calculation.

Why this happens: The problem states we must make at least one move, so the top-left cell cannot be an ending position if we start there. However, it can be a starting position for moves to other cells.

Solution: Add a check to skip score calculation for positions where no previous cell exists:

# Only update max_score if there was a valid previous position
if min_previous != inf:
    max_score = max(max_score, current_value - min_previous)

2. Incorrect Initialization of the Answer Variable

Another pitfall is initializing max_score to 0 instead of -inf. Since the grid contains positive integers and we're calculating differences, the maximum score could be negative (e.g., moving from a larger value to a smaller value).

Example: If the grid is [[10, 5], [8, 3]], all possible moves result in negative scores, and the answer should be -2 (from 5 to 3), not 0.

Solution: Always initialize to -inf:

max_score = -inf  # Not max_score = 0

3. Misunderstanding the Movement Rules

Some might incorrectly assume you can only move to adjacent cells (immediate right or immediate down), but the problem allows jumping to ANY cell that is below or to the right.

Incorrect approach:

# Wrong - only checking adjacent cells
if i > 0:
    min_previous = dp[i-1][j]  # Only immediate above
if j > 0:
    min_previous = dp[i][j-1]  # Only immediate left

Correct approach: The DP table propagates the minimum values through the grid, so checking dp[i-1][j] already contains the minimum from all cells that can reach (i-1, j), effectively allowing jumps.

4. Not Considering All Valid Starting Positions

A subtle pitfall is forgetting that we can start from any cell, not just the top-left corner. The DP approach handles this by storing min(current_value, min_previous) in dp[i][j], which allows each cell to potentially be a starting point.

Complete Corrected Code:

def maxScore(self, grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    max_score = -inf
  
    for i in range(rows):
        for j in range(cols):
            current_value = grid[i][j]
            min_previous = inf
          
            if i > 0:
                min_previous = min(min_previous, dp[i - 1][j])
            if j > 0:
                min_previous = min(min_previous, dp[i][j - 1])
          
            # Only update score if there's a valid previous position
            if min_previous != inf:
                max_score = max(max_score, current_value - min_previous)
          
            dp[i][j] = min(current_value, min_previous)
  
    return max_score