Maximum-sum Grid Path

01 · Question

Given a rectangular integer grid, return the largest sum on a path from its top-left to bottom-right cell, moving only right or down. Include both endpoints; values may be negative. An empty grid returns zero.

Example: [[1,-2],[3,4]] returns 8.

02 · Analysis

dp[r][c] is the best path sum ending at that cell. The preceding cell is either above or left, so take the better reachable predecessor and add the current value. Initialize the first row and column from their only legal predecessor rather than using zero for an illegal move; this handles negative grids. Fill row by row in O(RC) time and O(RC) auxiliary space. A rolling row reduces space to O(C) if only the value is required; store predecessor decisions if a path is required.

03 · Solution

Reference solution

1def max_sum_grid_path(grid):
2    if not grid or not grid[0]:
3        return 0
4    rows, cols = len(grid), len(grid[0])
5    dp = [[0] * cols for _ in range(rows)]
6    for r in range(rows):
7        for c in range(cols):
8            if r == 0 and c == 0:
9                dp[r][c] = grid[r][c]
10            elif r == 0:
11                dp[r][c] = dp[r][c-1] + grid[r][c]
12            elif c == 0:
13                dp[r][c] = dp[r-1][c] + grid[r][c]
14            else:
15                dp[r][c] = max(dp[r-1][c], dp[r][c-1]) + grid[r][c]
16    return dp[-1][-1]

Longest Increasing Subsequence

0/1 Subset Sum