Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Maximum Path Sum in a Triangle

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

Das lernst du

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

Problem

Übersetzung anzeigen

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.

Einschränkungen

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

Beispiele

Beispiel 1
Eingabe:
triangle = [
    [4],
    [7, 2],
    [1, 9, 5],
    [6, 3, 8, 2]
]

Erwartete Ausgabe:
expected = 28
Eingabe:
std::vector<std::vector<long long>> triangle = {
    {4},
    {7, 2},
    {1, 9, 5},
    {6, 3, 8, 2}
};

Erwartete Ausgabe:
long long expected = 28;
Eingabe:
long[][] triangle = new long[][] {
    new long[] {4},
    new long[] {7, 2},
    new long[] {1, 9, 5},
    new long[] {6, 3, 8, 2}
};

Erwartete Ausgabe:
long expected = 28;

Erläuterung

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

Beispiel 2
Eingabe:
triangle = [
    [-3],
    [5, -8],
    [-1, 2, 9]
]

Erwartete Ausgabe:
expected = 4
Eingabe:
std::vector<std::vector<long long>> triangle = {
    {-3},
    {5, -8},
    {-1, 2, 9}
};

Erwartete Ausgabe:
long long expected = 4;
Eingabe:
long[][] triangle = new long[][] {
    new long[] {-3},
    new long[] {5, -8},
    new long[] {-1, 2, 9}
};

Erwartete Ausgabe:
long expected = 4;

Erläuterung

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

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

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

Hinweis 2

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

Hinweis 3

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

Erwartete Komplexität

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

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.