Longest Increasing Subsequence
ניתנת לך רשימה של מספרים שלמים nums. תת־רצף משאיר חלק מהאיברים, בסדר המקורי שלהם, ומשמיט את השאר; האיברים שנשארים לא חייבים להיות סמוכים זה לזה. החזר את האורך של תת־הרצף הארוך ביותר שערכיו עולים ממש משמאל לימין. שני ערכים שווים ברצף אינם נחשבים לעלייה.
פונקציה
- numsinteger-array
- רשימת המספרים השלמים שמהם יש לבחור
- מחזירהinteger
- האורך של תת־הסדרה העולה ממש הארוכה ביותר
אילוצים
1 ≤ nums.length ≤ 2500-104 ≤ nums[i] ≤ 104
דוגמאות
- קלט
- nums = [3, 1, 8, 2, 5, 9, 4, 7]
- פלט
- 4
- הסבר
- השארת 1, 2, 5, 9 יוצרת תת־סדרה עולה באורך 4, וכך גם 1, 2, 5, 7 ו־1, 2, 4, 7. אין בחירה של חמישה ערכים ששומרת על סדר עולה, ולכן התשובה היא 4.
- קלט
- nums = [7, 7, 7, 7]
- פלט
- 1
- הסבר
- הערכים חייבים לעלות באופן ממשי, ולכן אף שני ערכי 7 לא יכולים להופיע באותה תת־סדרה. גם איבר יחיד נחשב, ולכן התשובה היא 1.
- קלט
- nums = [12, -4, 0, 25, -10, 3, 16, 5]
- פלט
- 4
- הסבר
- -4, 0, 3, 16 אורכו 4 (גם ל-4, 0, 3, 5 יש אורך כזה). התחלה מהאיבר הראשון, 12, נותנת לך רק שני ערכים, למשל 12, 25: תת-הסדרה הטובה ביותר לא חייבת להתחיל מההתחלה.
+20 בדיקות נסתרות בשליחה
שאלת המשך
האם תוכלו להחזיר את אחת מתתי־הסדרות העולות הארוכות ביותר עצמן, ולא רק את אורכן, ועדיין לפעול בזמן O(n log n)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
קשה לתאר ישירות את תת־הסדרה הטובה ביותר בכל הרשימה. שאלו שאלה ממוקדת יותר עבור כל אינדקס
i: מהי תת־הסדרה העולה הארוכה ביותר שמסתיימת בדיוק ב־nums[i]?תת־רצף שמסתיים ב־
nums[i]הוא אוnums[i]לבדו, או ממשיך את תת־הרצף הטוב ביותר שמסתיים באיזשהוnums[j] < nums[i]מוקדם יותר. בוחרים אתjהטוב ביותר ומוסיפים אחד. התשובה היא הערך הגדול ביותר מבין הערכים האלה, בלי קשר למקום שבו הוא מסתיים.כדי לרדת מתחת ל־
O(n²), שמור עבור כל אורך רק את הערך הקטן ביותר שבו תת־רצף באורך הזה יכול להסתיים. הערכים האלה נשארים ממוינים, ולכן חיפוש בינארי יגיד לך אם מספר חדש מאריך את הרצף הארוך ביותר או מחליף ערך סיום.
פתרון
תת־רצף יכול לדלג על כל איבר, ולכן לרשימה של n מספרים יש 2^n תתי־רצפים, הרבה יותר מדי מכדי לבדוק את כולם. הפתרון באמצעות תכנות דינמי הוא לשאול שאלה ממוקדת יותר עבור כל אינדקס: מהו אורכו של תת־הרצף העולה הטוב ביותר שמסתיים בדיוק כאן? כך מתקבלת טבלה בגודל O(n²). הגרסה המהירה ביותר שומרת מספר אחד לכל אורך — הערך הקטן ביותר שבו תת־רצף באורך הזה יכול להסתיים — וממקמת כל איבר חדש באמצעות חיפוש בינארי.
קח או דלג על כל רכיב
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
עוברים על הרשימה ומקבלים החלטה אחת לכל איבר: להשאיר אותו או לדלג עליו. אפשר להשאיר את nums[i] רק אם הוא גדול מהערך האחרון שהשארת. פונקציה רקורסיבית longest(i, prev) עונה על השאלה: אם האיבר האחרון שהושאר נמצא באינדקס prev (או -1 אם עדיין לא השארנו שום איבר), כמה איברים נוספים אפשר להוסיף החל מאינדקס i?
דילוג נותן את longest(i+1, prev). השארה, כשהיא מותרת, נותנת את 1 + longest(i+1, i). התשובה היא הגדול מבין השניים, ואחרי סוף הרשימה אי אפשר להוסיף עוד, ולכן התוצאה שם היא 0. כל תת-סדרה עולה היא מסלול אחד של בחירות להשאיר ולדלג, ולכן החיפוש לא יכול לפספס את הטובה ביותר.
הפעולה איטית כי שני הענפים ממשיכים בכל פעם שהערכים עולים. ברשימה כמו 1, 2, 3, ..., n מספר הקריאות מוכפל בכל איבר: 2 בחזקת 40 הוא כבר בערך 10^12 קריאות, ובבדיקות הגדולות יש 2500 איברים. ובכל זאת, longest(i, prev) תלויה רק בזוג (i, prev), ולכן יש לכל היותר n² שאלות שונות. הגישה הבאה היא לשאול כל אחת מהן פעם אחת.
אלגוריתם
- כתבו את
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[i] הוא nums[j] כלשהו, כך ש־j < i ו־nums[j] < nums[i], והחלק עד אליו צריך להיות ארוך ככל האפשר. לכן ending[i] = 1 + max(ending[j]) עבור אותם ערכי j. מקרה בסיס: כל איבר לבדו הוא תת־סדרה, לכן הערך ההתחלתי של ending[i] הוא 1. סדר: ending[i] קורא רק אינדקסים קטנים ממנו, לכן ממלאים אותו משמאל לימין.
עבור [3, 1, 8, 2, 5, 9, 4, 7] הטבלה היא [1, 1, 2, 2, 3, 4, 3, 4]. למשל, אחרי 3, 1 או 2 יכול לבוא 5, והטוב ביותר מביניהם הוא 2 עם ending = 2, לכן ending[4] = 3. התשובה היא הערך הגדול ביותר, 4, ולא הערך האחרון: תת־הסדרה הטובה ביותר יכולה להסתיים בכל מקום.
כל אינדקס בודק פעם אחת כל אינדקס שקודם לו, לכן מספר הפעולות הוא 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 שמסתיימת ב־t מכילה תת־סדרה באורך k+1 שמסתיימת בערך קטן מ־t. לכן, עבור כל ערך חדש x, מחפשים בחיפוש בינארי את הזנב הראשון שערכו ≥ x. אם אין כזה, x גדול מכל הזנבות ומאריך את תת־הסדרה הארוכה ביותר, ולכן מוסיפים אותו לסוף. אחרת, מחליפים את הזנב הזה ב־x: תת־הסדרה שקצרה באחד מסתיימת בערך קטן מ־x, ולכן הוספת x נותנת אותו אורך עם ערך סיום קטן יותר.
עבור [3, 1, 8, 2, 5, 9, 4, 7], 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 עצמה אינה תת־סדרה; רק לאורך שלה יש משמעות. השיטה נקראת גם מיון סבלנות (patience sorting), על שם משחק הקלפים שבו כל זנב הוא הקלף העליון בערימה.
עבור כל איבר מבצעים חיפוש בינארי אחד על פני לכל היותר n זנבות: כ־2500 × 12 = 30,000 צעדים עבור הקלט הגדול ביותר.
אלגוריתם
- התחל עם רשימה ריקה
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 השני אחרי הראשון וסופרת ערכים שווים כתת־רצף ארוך יותר. - התייחסות ל־
tailsכאילו הוא תת־הרצף עצמו. הערכים שלו יכולים להגיע מתתי־רצפים שונים, לכן יש להדפיס אותו רק אם עוקבים בנפרד אחר ההורים. - פתרון בטעות של הגרסה הרציפה. ב־
[3, 1, 8, 2, 5, 9, 4, 7]הרצף העולה הארוך ביותר של איברים סמוכים הוא 2, 5, 9 (באורך 3), בעוד שהתשובה היא 4. - ב־Lua וב־R, המערכים מתחילים באינדקס 1, לכן סמן מבוסס־0 כמו
prev = -1הופך ל־0, והחיפוש הבינארי מתבצע באינדקסים מ־1 ועד לגודל הנוכחי.
שאלות נפוצות4
מהי סיבוכיות הזמן של תת-הסדרה העולה הארוכה ביותר?
שיטת tails פועלת בזמן O(n log n) ובמקום O(n): חיפוש בינארי אחד לכל איבר. טבלת התכנות הדינמי על פני כל זוג אינדקסים דורשת זמן O(n²), וניסיון של כל תת־רצף דורש O(2ⁿ). עבור n = 2500 מדובר בכ־30,000, 3 מיליון ומספר אסטרונומי של צעדים.
למה שיטת המיון בסבלנות נותנת את האורך הנכון?
אחרי כל איבר, tails[k] מכיל את הערך הקטן ביותר שכל תת־רצף עולה באורך k+1 שנראה עד כה יכול להסתיים בו. מוסיפים איבר רק כאשר x גדול מכל ערכי הסיום, כלומר כעת קיים תת־רצף שאורכו גדול באחד מכל תת־רצף קודם. החלפה לעולם אינה משנה את האורך, אלא רק מקטינה את ערך הסיום, ולכן אורך הרשימה הוא תמיד אורך תת־הרצף העולה הארוך ביותר.
איך מוצאים את תת־הסדרה העולה הארוכה ביותר עצמה, ולא רק את אורכה?
תעדו הורה עבור כל איבר. בטבלת O(n²), ההורה של i הוא ה-j שנתן ל-ending[i] את הערך שלו. בשיטת הזנבות, שמרו את האינדקס של האיבר שמאחורי כל זנב, והגדירו את ההורה של איבר כאינדקס ששמור מיקום אחד משמאלו כאשר מציבים אותו. לאחר מכן עקבו אחר ההורים לאחור מסוף תת-הסדרה הארוכה ביותר והפכו את התוצאה.
איך מוצאים במקום זאת את תת־הסדרה הארוכה ביותר שאינה יורדת?
אפשר שכנים שווים. בטבלה, השתמשו ב־nums[j] ≤ nums[i]. בשיטת הזנבות, חפשו את הזנב הראשון שגדול ממש מ־x במקום גדול ממנו או שווה לו, כך שערך שווה יאריך את הרשימה במקום להחליף זנב. [7, 7, 7, 7] מחזיר אז 4.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def lengthOfLIS(nums):
# כתבו כאן את הקודמקרה 1
מקרה 2
מקרה 3
קלט
nums = [3, 1, 8, 2, 5, 9, 4, 7]
צפוי
4