All challenges
Medium 0 solved 0% acceptance

Maximum Path Sum in a Triangle

Find the largest sum on a path from the top of a number triangle to its bottom row.

What you'll learn

  • Replace exponential search with dynamic programming
  • Combine results from the row below
  • Handle negative values and empty input

Problem

A number triangle has one value on row 0, two on row 1, and so on. Start at the top and move down one row at a time, each time to the value directly below or the one below and to the right (from position i to i or i + 1). Find the path whose values add up to the most. Trying every path doubles the work each row; working upward from the bottom row keeps it quadratic.

Implement triangle_max_path_sum(triangle).

Input

triangle: The rows from top to bottom; row r has r + 1 values, which may be negative.

Output

Return the largest possible sum of a top-to-bottom path. An empty triangle returns 0.

Constraints

0 ≤ rows ≤ 100; −1000 ≤ value ≤ 1000

Examples

Example 1
Input:
triangle = [
    [4],
    [7, 2],
    [1, 9, 5],
    [6, 3, 8, 2]
]

Expected output:
expected = 28
Input:
std::vector<std::vector<long long>> triangle = {
    {4},
    {7, 2},
    {1, 9, 5},
    {6, 3, 8, 2}
};

Expected output:
long long expected = 28;
Input:
long[][] triangle = new long[][] {
    new long[] {4},
    new long[] {7, 2},
    new long[] {1, 9, 5},
    new long[] {6, 3, 8, 2}
};

Expected output:
long expected = 28;

Explanation

The best path is 4, 7, 9, 8 (position 0, 0, 1, 2), for 28.

Example 2
Input:
triangle = [
    [-3],
    [5, -8],
    [-1, 2, 9]
]

Expected output:
expected = 4
Input:
std::vector<std::vector<long long>> triangle = {
    {-3},
    {5, -8},
    {-1, 2, 9}
};

Expected output:
long long expected = 4;
Input:
long[][] triangle = new long[][] {
    new long[] {-3},
    new long[] {5, -8},
    new long[] {-1, 2, 9}
};

Expected output:
long expected = 4;

Explanation

With negatives, −3, 5, 2 gives 4 while −3, −8, 9 gives −2, so the answer is 4.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Start from the bottom row: the best path from a bottom cell is just its value.

Hint 2

The best path from a cell is its value plus the larger best of the two cells below it.

Hint 3

After processing every row upward, the top cell holds the answer.

Expected complexity

O(rows²) time, O(rows) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.