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، وكذلك 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. بدءًا من العنصر الأول، 12، لا يمنحك سوى قيمتين، مثل 12, 25: ليس من الضروري أن تبدأ أفضل سلسلة فرعية من البداية.
سؤال إضافي
هل يمكنك إرجاع إحدى أطول المتتاليات الفرعية المتزايدة نفسها، إلى جانب طولها، مع الحفاظ على زمن تنفيذ 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) هو أكبر عدد من العناصر التي لا يزال بإمكانك إضافتها بدءًا من الفهرس i، عندما يكون العنصر الأخير الذي احتفظت به عند prev (أو -1). يؤدي التخطي إلى longest(i+1, prev)؛ ويؤدي الاحتفاظ إلى 1 + longest(i+1, i). كل متتالية متزايدة تمثل مسارًا واحدًا من هذه الاختيارات.
بالنسبة إلى 1, 2, 3, ..., n، يظل كلا الفرعين متاحًا، ويتضاعف عدد الاستدعاءات مع كل عنصر: إذ إن 2^40 يساوي بالفعل نحو 10^12. ومع ذلك، لا يتجاوز عدد الأزواج المختلفة (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[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]
الإخراج المتوقع
4