Longest Increasing Subsequence

Q: מהי סיבוכיות הזמן של תת־הסדרה העולה הארוכה ביותר?

שיטת tails רצה בזמן O(n log n) ומשתמשת במקום O(n) : חיפוש בינארי אחד לכל איבר. הטבלה על כל זוג אינדקסים דורשת זמן O(n²) , וניסיון של כל תת־הסדרות דורש O(2ⁿ) .

Q: איך מוצאים במקום זאת את תת-הסדרה הארוכה ביותר שאינה יורדת?

אפשר שכנים שווים. בטבלה, השתמשו ב- nums[j] ≤ nums[i] . בשיטת הזנבות, חפשו את הזנב הראשון שגדול ממש מ- x , כך שערך שווה יאריך את הרשימה במקום להחליף זנב. במקרה כזה, [7, 7, 7, 7] מחזיר 4.

בינוניתכנון דינמי חיפוש בינארי

+10

ניתנת לך רשימה של מספרים שלמים nums. תת־רצף משאיר חלק מהאיברים בסדר המקורי שלהם ומשמיט את השאר; האיברים שנשארו לא חייבים להיות סמוכים זה לזה. החזר את האורך של תת־הרצף הארוך ביותר שערכיו עולים באופן ממש משמאל לימין. שני ערכים שווים ברצף אינם נחשבים לעלייה.

פונקציה

lengthOfLIS(nums: integer-array) → integer

numsinteger-array: רשימת המספרים השלמים שמהם יש לבחור
מחזירהinteger: אורך תת־הסדרה העולה ממש הארוכה ביותר

אילוצים

1 ≤ nums.length ≤ 2500
-10⁴ ≤ nums[i] ≤ 10⁴

דוגמאות

קלט: nums = [3, 1, 8, 2, 5, 9, 4, 7]
פלט: 4
הסבר: 1, 2, 5, 9 עולים, וכך גם 1, 2, 5, 7 וגם 1, 2, 4, 7: אורך 4. אין בחירה של חמישה ערכים שממשיכה לעלות.

שאלת המשך

האם אפשר להחזיר תת־רצף עולה הארוך ביותר עצמו, לצד אורכו, ועדיין לפעול בזמן O(n log n)?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

לרשימה של n מספרים יש 2^n תתי־רצפים, יותר מדי מכדי לבדוק. אם נשאל, עבור כל אינדקס, מה אורכו של תת־הרצף העולה הטוב ביותר שמסתיים בדיוק שם, נקבל טבלה של O(n²). הגרסה המהירה ביותר שומרת, עבור כל אורך, את הערך הקטן ביותר שתת־רצף באורך הזה יכול להסתיים בו, וממקמת כל איבר באמצעות חיפוש בינארי.

קח או דלג על כל איבר

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

קבעו עבור כל איבר אם להשאיר אותו; אפשר להשאיר את nums[i] רק כאשר הוא גדול מהערך האחרון שהושאר. longest(i, prev) הוא מספר האיברים המרבי שאפשר עדיין להוסיף החל מהאינדקס i, כאשר האיבר האחרון שהושאר נמצא ב-prev (או -1). דילוג נותן longest(i+1, prev); השארה נותנת 1 + longest(i+1, i). כל תת-רצף עולה הוא מסלול אחד של הבחירות האלה.

עבור 1, 2, 3, ..., n שני הענפים נשארים פתוחים והקריאות מוכפלות עם כל איבר: 2^40 הוא כבר בערך 10^12. עם זאת, יש לכל היותר n² זוגות שונים (i, prev).

אלגוריתם

כתבו longest(i, prev), כאשר prev הוא האינדקס של האיבר האחרון שנשמר, או -1.
אם i נמצא מעבר לסוף, החזירו 0.
דלגו על nums[i]: best = longest(i+1, prev).
אם prev הוא -1 או nums[i] > nums[prev], שמרו אותו: best = max(best, 1 + longest(i+1, i)).
החזירו את best. התשובה היא longest(0, -1).

def lengthOfLIS(nums):
    def longest(i, prev):
        # The longest increasing subsequence of nums[i:] whose values all exceed nums[prev].
        # prev is -1 while nothing has been taken.
        if i == len(nums):
            return 0
        best = longest(i + 1, prev)  # skip nums[i]
        if prev == -1 or nums[i] > nums[prev]:
            best = max(best, 1 + longest(i + 1, i))  # take nums[i]
        return best

    return longest(0, -1)

תת־הסדרה הארוכה ביותר שמסתיימת בכל אינדקס

האינטואיציה

נגדיר את ending[i] כאורך תת־הסדרה העולה הארוכה ביותר שהאיבר האחרון שלה הוא nums[i]. האיבר שלפני nums[i], אם יש כזה, הוא nums[j] כלשהו שעבורו j < i וגם nums[j] < nums[i], והחלק שמסתיים בו צריך להיות ארוך ככל האפשר. לכן ending[i] = 1 + max(ending[j]) עבור אותם ערכי j, או 1 אם אין כאלה. נמלא את המערך משמאל לימין.

עבור [3, 1, 8, 2, 5, 9, 4, 7], הטבלה היא [1, 1, 2, 2, 3, 4, 3, 4]: 5 יכול לבוא אחרי 3, 1 או 2, והטוב ביותר מביניהם הוא באורך 2, לכן ending[4] = 3. התשובה היא הערך הגדול ביותר, מכיוון שתת־הסדרה הטובה ביותר יכולה להסתיים בכל מקום.

n(n-1)/2 השוואות: כ־3.1 × 10^6 עבור n = 2500.

אלגוריתם

צרו את ending כשכל הערכים בו מוגדרים ל־1.
עבור כל i, משמאל לימין, בדקו כל j < i.
אם nums[j] < nums[i], הגדירו את ending[i] ל־ending[j] + 1 אם הערך הזה גדול יותר.
החזירו את הערך הגדול ביותר ב־ending.

def lengthOfLIS(nums):
    n = len(nums)
    # ending[i]: the longest increasing subsequence that ends with nums[i]
    ending = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i] and ending[j] + 1 > ending[i]:
                ending[i] = ending[j] + 1
    return max(ending)

הזנבות הקטנים ביותר באמצעות חיפוש בינארי

האינטואיציה

עבור כל אורך, שומרים רק את הערך הקטן ביותר שבו יכולה להסתיים תת־סדרה עולה באורך הזה: tails[k] עבור אורך k+1. סיום בערך קטן יותר לעולם אינו גרוע יותר: כל מה שיכול לבוא אחרי 9 יכול לבוא גם אחרי 5. tails נשארת בסדר עולה ממש: מסירים את הערך האחרון מתת־סדרה עולה באורך k+2 ומקבלים תת־סדרה באורך k+1 שמסתיימת בערך קטן יותר.

עבור כל x, מבצעים חיפוש בינארי כדי למצוא את הזנב הראשון ≥ x. אם אין כזה, מוסיפים את x לסוף: כך מרחיבים את תת־הסדרה הארוכה ביותר. אחרת, מחליפים את הזנב הזה ב־x: תת־הסדרה שאורכה קצר באחד מסתיימת בערך קטן מ־x, ולכן x מאפשר להשיג אותו אורך עם ערך סיום קטן יותר.

לדוגמה 1, tails משתנה כך: [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7]: האורך הוא 4. ב־[1, 2, 4, 9] ה־4 הגיע אחרי ה־9, ולכן רק האורך של tails הוא בעל משמעות.

אלגוריתם

התחל עם רשימה ריקה tails.
עבור כל x בתוך nums, חפש בחיפוש בינארי את האינדקס הראשון k שעבורו tails[k] ≥ x.
אם אין איבר זנב שגדול או שווה ל־x, הוסף את x בסוף.
אחרת, הצב tails[k] = x.
החזר את האורך של tails.

from bisect import bisect_left


def lengthOfLIS(nums):
    # tails[k]: the smallest last value of any increasing subsequence of length k + 1
    tails = []
    for x in nums:
        k = bisect_left(tails, x)  # the first tail that is >= x
        if k == len(tails):
            tails.append(x)  # x extends the longest subsequence so far
        else:
            tails[k] = x  # x is a smaller ending for length k + 1
    return len(tails)

מלכודות ומקרי קצה

החזרת ending[n-1] במקום הערך הגדול ביותר. עבור [1, 2, 3, 0] הערך האחרון הוא 1, אבל התשובה היא 3.
השוואה באמצעות ≤ במקום <. עבור [7, 7, 7, 7] יש להחזיר 1, לא 4.
בגרסת tails, חיפוש הזנב הראשון שעבורו > x במקום ≥ x. כך ה-7 השני יתווסף אחרי הראשון, וערכים שווים ייספרו כעולים.
פתרון שגוי של גרסת הרצף הרציף. בדוגמה 1, הרצף העולה הארוך ביותר של שכנים הוא 2, 5, 9 (באורך 3), בעוד שהתשובה היא 4.
השארת אינדקסים שמתחילים ב-0 ב-Lua או ב-R, שבהן מערכים מתחילים ב-1. הסמן prev = -1 הופך ל-0, והחיפוש הבינארי מתבצע באינדקסים 1 עד הגודל הנוכחי.

שאלות נפוצות3

מהי סיבוכיות הזמן של תת־הסדרה העולה הארוכה ביותר?

שיטת tails רצה בזמן O(n log n) ומשתמשת במקום O(n): חיפוש בינארי אחד לכל איבר. הטבלה על כל זוג אינדקסים דורשת זמן O(n²), וניסיון של כל תת־הסדרות דורש O(2ⁿ).

מהו מיון סבלני בהקשר של תת־הסדרה העולה הארוכה ביותר?

זוהי שיטת הזנבות, שנקראת על שם משחק קלפים. כל זנב הוא הקלף העליון בערימה: קלף מונח על הערימה השמאלית ביותר שהקלף העליון שלה גדול מערכו או שווה לו, או מתחיל ערימה חדשה. מספר הערימות הוא התשובה.

איך מוצאים במקום זאת את תת-הסדרה הארוכה ביותר שאינה יורדת?

אפשר שכנים שווים. בטבלה, השתמשו ב-nums[j] ≤ nums[i]. בשיטת הזנבות, חפשו את הזנב הראשון שגדול ממש מ-x, כך שערך שווה יאריך את הרשימה במקום להחליף זנב. במקרה כזה, [7, 7, 7, 7] מחזיר 4.

def lengthOfLIS(nums):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

nums = [3, 1, 8, 2, 5, 9, 4, 7]

הפלט הצפוי

Longest Increasing Subsequence

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

קח או דלג על כל איבר

תת־הסדרה הארוכה ביותר שמסתיימת בכל אינדקס

הזנבות הקטנים ביותר באמצעות חיפוש בינארי

מלכודות ומקרי קצה

שאלות נפוצות3

בעיות דומות