Maximum Triangle Path Sum, Overall and Through a Required Cell

A number triangle has n rows. Row i (0-indexed) holds i + 1 integers, so triangle[i][j] exists for 0 <= j <= i.

A path starts at the single value in row 0 and moves down one row at a time until it reaches row n - 1. From position j in row i, the next step goes to position j or position j + 1 in row i + 1. The sum of a path is the total of all n values it visits.

Compute two values:

1. best_overall: the maximum sum over all top-to-bottom paths.
2. best_through: the maximum sum over the top-to-bottom paths that pass through the fixed cell (r, c), that is, the paths that visit triangle[r][c].

Return [best_overall, best_through].

Function Signature

def triangle_max_paths(triangle: list[list[int]], r: int, c: int) -> list[int]:

Rules

• Every path visits exactly one value in each row, starting at the apex and ending in the bottom row.
• Every cell of the triangle lies on at least one top-to-bottom path, so best_through always exists.
• Values may be negative; a path cannot stop early or skip a row to avoid them.

Constraints

• 1 <= n <= 200
• len(triangle[i]) == i + 1 for every row i
• -10^4 <= triangle[i][j] <= 10^4
• 0 <= r <= n - 1 and 0 <= c <= r
• Every path sum lies between -2 * 10^6 and 2 * 10^6, well inside the 32-bit range.

Examples

Example 1

Input: triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]], r = 1, c = 0
Output: [21, 18]

The best path overall is 2 → 4 → 7 → 8 = 21. A path through the 3 in row 1 reaches at most 2 → 3 → 5 → 8 = 18.

Example 2

Input: triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]], r = 3, c = 0
Output: [21, 15]

Only one path reaches the bottom-left corner: 2 → 3 → 6 → 4 = 15.

Example 3

Input: triangle = [[-5]], r = 0, c = 0
Output: [-5, -5]