أطول تتابع متزايد
برمجة ديناميكية O(n^2) ثم حيلة O(n log n)
أطول تتابع متزايد درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ما المقصود بـ LIS
تحافظ المتتالية الجزئية على الترتيب، لكنها تتخطى بعض العناصر. أما أطول متتالية متزايدة فهي أطول متتالية من هذا النوع تتزايد بصرامة.
a = [3, 1, 4, 1, 5, 9, 2]متتالية جزئية، لا مصفوفة جزئية
على عكس المصفوفة الجزئية، لا يلزم أن تكون LIS متجاورة. يمكنك تخطي الأعداد الأصغر للاستمرار في زيادة السلسلة.
حالة DP ذات التعقيد O(n^2)
لتكن dp[i] طول LIS التي تنتهي عند الفهرس i. كل عنصر يمثل متتالية جزئية طولها واحد على الأقل بمفرده.
dp = [1] * nانتقال O(n^2)
لكل i، افحص كل j سابق. إذا كان a[j] أصغر، فمدّد المتتالية: dp[i] = max(dp[i], dp[j] + 1).
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)استخرج الإجابة
النتيجة هي أكبر قيمة في الجدول، لأن LIS قد تنتهي في أي موضع، وليس عند الفهرس الأخير فقط.
answer = max(dp)لماذا قد يؤدي O(n^2) إلى تجاوز الوقت
تستغرق الحلقة المزدوجة O(n squared). وعندما تقترب n من 100000، يصبح ذلك بطيئًا جدًا وتحصل على حكم تجاوز المهلة الزمنية.
فكرة فرز الصبر
تحتفظ الطريقة الأسرع بقائمة تضم أصغر ذيل ممكن لكل طول من أطوال المتتاليات، على غرار فرز الصبر.
tails = []استخدم bisect لتحديد الموضع
لكل عدد، ابحث ثنائيًا عن موضعه بين الذيول باستخدام bisect_left، لتحصل على تعقيد إجمالي O(n log n).
from bisect import bisect_leftمدّد أو استبدل
إذا كان الموضع بعد نهاية القائمة، فاستخدم append لزيادة طول LIS. وإلا، فاستبدل ذلك الذيل بالقيمة الأصغر.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xالطول في tails
عند انتهاء الفحص، تكون len(tails) هي طول LIS. أما القائمة نفسها فلا تمثل المتتالية دائمًا؛ فالطول وحده دقيق.
answer = len(tails)متزايدة بصرامة مقابل غير تناقصية
للحالة غير التناقصية، استخدم bisect_right بدلًا من ذلك، حتى تتمكن القيم المتساوية من تمديد السلسلة.
from bisect import bisect_rightتحقق سريع
أي طريقة تجد طول LIS في O(n log n)؟
مراجعة: من n^2 إلى n log n
يمكنك الآن حل LIS بطريقتين. إن DP ذات O(n^2) بسيطة، بينما تتوسع طريقة الذيول مع bisect لتتعامل مع المدخلات الكبيرة وتتجنب تجاوز المهلة الزمنية.
الأسئلة الشائعة
هل درس «أطول تتابع متزايد» مجاني؟
نعم — نص درس «أطول تتابع متزايد» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «أطول تتابع متزايد»؟
برمجة ديناميكية O(n^2) ثم حيلة O(n log n) تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «أطول تتابع متزايد»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.