Longest Increasing Subsequence

Q: ما هو التعقيد الزمني لأطول متتالية متزايدة؟

تعمل طريقة tails في زمن O(n log n) ومساحة O(n) : بحث ثنائي واحد لكل عنصر. يستغرق جدول البرمجة الديناميكية على كل زوج من الفهارس زمن O(n²) ، بينما تستغرق تجربة كل تتابع O(2ⁿ) . عند n = 2500 ، يعادل ذلك نحو 30,000 و3 ملايين وعددًا فلكيًا من الخطوات.

Q: لماذا تعطي طريقة الفرز بالصبر الطول الصحيح؟

بعد كل عنصر، تحتوي tails[k] على أصغر قيمة يمكن أن تنتهي بها أي متتالية فرعية متزايدة طولها k+1 شوهدت حتى الآن. لا تحدث الإضافة إلا عندما تكون x أكبر من جميع القيم النهائية، ما يعني أن متتالية فرعية أطول بواحد من أي متتالية سابقة أصبحت موجودة الآن. لا يؤدي الاستبدال إلى تغيير الطول، بل يخفض قيمة النهاية فحسب، لذا يكون طول القائمة دائمًا هو طول أطول متتالية فرعية متزايدة.

Q: كيف تحصل على أطول متتالية متزايدة فعلية، وليس طولها فقط؟

سجّل عنصرًا أبًا لكل عنصر. في جدول O(n²) ، يكون أب i هو j الذي أعطى ending[i] قيمتها. في طريقة الذيول، خزّن فهرس العنصر الموجود خلف كل ذيل، واجعل أب العنصر هو الفهرس المخزّن في الموضع الذي يسبقه مباشرةً عند وضعه. ثم تتبّع الآباء عائدًا من نهاية أطول تتابع فرعي، واعكس النتيجة.

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 متتالية جزئية متزايدة طولها 4، وكذلك الحال مع 1، 2، 5، 7 و1، 2، 4، 7. لا يوجد اختيار من خمس قيم يواصل الارتفاع، لذا فالإجابة هي 4.

+20 اختبارات مخفية عند الإرسال

سؤال إضافي

هل يمكنك إرجاع إحدى أطول المتتاليات الفرعية المتزايدة نفسها، وليس طولها فقط، مع الاستمرار في التنفيذ بزمن O(n log n)؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

يمكن للمتتالية الجزئية تخطي أي عنصر، لذا فإن قائمةً تضم 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]. على سبيل المثال، يمكن أن يأتي 5 بعد 3 أو 1 أو 2، وأفضل هذه الخيارات هو 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 ليست متتالية فرعية بحد ذاتها؛ طولها وحده هو ما له معنى. تُسمى هذه الطريقة أيضًا الفرز بالصبر، نسبةً إلى لعبة الورق التي يكون فيها كل ذيل هو الورقة العليا في كومة.

تتطلب معالجة كل عنصر عملية بحث ثنائي واحدة على الأكثر عبر 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، لذا تتحول علامة prev = -1 ذات الفهرسة التي تبدأ من 0 إلى 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]

المتوقع

Longest Increasing Subsequence

الدالة

القيود

أمثلة

تلميحات

الحل

خذ كل عنصر أو تخطَّاه

أطول تتابع جزئي ينتهي عند كل فهرس

أصغر النهايات باستخدام البحث الثنائي

أخطاء شائعة وحالات حدّية

أسئلة شائعة4

مسائل مشابهة