मध्यम 0 हल किए गए 0% स्वीकृति

Maximum Path Sum in a Triangle

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

आप क्या सीखेंगे

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

समस्या

अनुवाद दिखाएँ

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.

सीमाएँ

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

उदाहरण

उदाहरण 1
इनपुट:
triangle = [
    [4],
    [7, 2],
    [1, 9, 5],
    [6, 3, 8, 2]
]

अपेक्षित आउटपुट:
expected = 28
इनपुट:
std::vector<std::vector<long long>> triangle = {
    {4},
    {7, 2},
    {1, 9, 5},
    {6, 3, 8, 2}
};

अपेक्षित आउटपुट:
long long expected = 28;
इनपुट:
long[][] triangle = new long[][] {
    new long[] {4},
    new long[] {7, 2},
    new long[] {1, 9, 5},
    new long[] {6, 3, 8, 2}
};

अपेक्षित आउटपुट:
long expected = 28;

व्याख्या

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

उदाहरण 2
इनपुट:
triangle = [
    [-3],
    [5, -8],
    [-1, 2, 9]
]

अपेक्षित आउटपुट:
expected = 4
इनपुट:
std::vector<std::vector<long long>> triangle = {
    {-3},
    {5, -8},
    {-1, 2, 9}
};

अपेक्षित आउटपुट:
long long expected = 4;
इनपुट:
long[][] triangle = new long[][] {
    new long[] {-3},
    new long[] {5, -8},
    new long[] {-1, 2, 9}
};

अपेक्षित आउटपुट:
long expected = 4;

व्याख्या

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

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

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

संकेत 2

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

संकेत 3

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

अपेक्षित जटिलता

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

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।