ماذا يعني LDS في الخوارزميات وهياكل البيانات؟ الشرح الصحيح

إذا صادفت الاختصار LDS أثناء دراستك للخوارزميات وهياكل البيانات أو في مسائل البرمجة التنافسية، فالمعنى الأرجح هو «أطول متتالية فرعية متناقصة» (Longest Decreasing Subsequence). إنه مسألة كلاسيكية في البرمجة الديناميكية، وهي الشقيقة المباشرة لمسألة LIS الأشهر (أطول متتالية فرعية متزايدة). أي أن السؤال ببساطة: بالنظر إلى مصفوفة من الأرقام، ما طول أطول سلسلة من عناصرها تسير في ترتيب تنازلي؟

انتبه إلى فخ شائع هنا: بعض المواقع تخلط LDS مع مصطلح آخر تمامًا اسمه Linked Data Signature (توقيع البيانات المترابطة)، وهو مفهوم من عالم التشفير والويب الدلالي، ولا علاقة له بمنهج الخوارزميات وهياكل البيانات. لذلك إن كنت طالب علوم حاسوب أو تحلّ مسائل خوارزميات، فأنت غالبًا تبحث عن المعنى الأول: أطول متتالية فرعية متناقصة.

ما الفرق بين «المتتالية الفرعية» و«السلسلة الفرعية»؟

هذا أهم فرق يجب أن تفهمه قبل حل المسألة، وهو مصدر أخطاء كثيرة:

• المتتالية الفرعية (Subsequence): نأخذ عناصر من المصفوفة مع الحفاظ على ترتيبها الأصلي، لكن يُسمح بتجاوز عناصر. فليست العناصر مضطرة لأن تكون متجاورة.
• السلسلة الفرعية المتصلة (Substring / Subarray): يجب أن تكون العناصر متجاورة دون فجوات.

في مسألة LDS نتعامل مع النوع الأول. فمثلًا في المصفوفة [8, 3, 6, 2, 5, 1, 4] تُعدّ 8, 6, 5, 4 متتالية فرعية متناقصة صحيحة رغم أن عناصرها غير متجاورة.

مثال محلول خطوة بخطوة

لنأخذ المصفوفة [8, 3, 6, 2, 5, 1, 4] ونحسب طول أطول متتالية فرعية متناقصة.

نعرّف dp[i] بأنه طول أطول متتالية متناقصة تنتهي عند العنصر رقم i. القاعدة:

dp[i] = 1 + أكبر قيمة dp[j] لكل عنصر سابق j أكبر من العنصر i.

نطبّقها:

1. العنصر 8 → dp = 1
2. العنصر 3 (يسبقه 8) → dp = 2
3. العنصر 6 (يسبقه 8) → dp = 2
4. العنصر 2 (يسبقه 8 و3 و6) → dp = 3
5. العنصر 5 (يسبقه 8 و6) → dp = 3
6. العنصر 1 (تسبقه عناصر أكبر عدة) → dp = 4
7. العنصر 4 (يسبقه 8 و6 و5) → dp = 4

جدول dp يصبح [1, 2, 2, 3, 3, 4, 4]، والجواب هو أكبر قيمة فيه أي 4. ومن أمثلة المتتاليات التي تحقق هذا الطول: 8, 6, 5, 4 أو 8, 3, 2, 1.

طريقة الحل بالبرمجة الديناميكية

الحل المباشر يكلّف زمنًا مقداره O(n²)، وهو كافٍ لأغلب التمارين والمصفوفات المتوسطة الحجم. إليك الفكرة بلغة شبيهة بالبرمجة:

function LDS(a):
    n = length(a)
    dp = array of n ones
    for i from 1 to n-1:
        for j from 0 to i-1:
            if a[j] > a[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
    return max(dp)

إذا أردت الحل الأسرع بزمن O(n log n)، فهناك حيلة أنيقة: أطول متتالية متناقصة في مصفوفة تساوي أطول متتالية متزايدة (LIS) في المصفوفة نفسها بعد عكس ترتيبها أو قلب إشارات عناصرها. بذلك تستفيد من خوارزمية LIS المعروفة القائمة على البحث الثنائي.

LDS أم LIS؟ مقارنة سريعة

المسألتان متطابقتان في الفكرة ومختلفتان في اتجاه الترتيب فقط:

الجانب	LDS (متناقصة)	LIS (متزايدة)
اتجاه الترتيب	تنازلي	تصاعدي
شرط الانتقال	العنصر السابق أكبر	العنصر السابق أصغر
التعقيد الزمني الأساسي	O(n²)	O(n²)
النسخة المُحسّنة	O(n log n)	O(n log n)
الحيلة	LIS على المصفوفة المعكوسة	—

لهذا السبب يكفي أن تتقن إحداهما لتحل الأخرى فورًا.

نصيحة عملية وخطأ شائع

الخطأ الأكثر تكرارًا هو الخلط بين «المتناقصة بصرامة» و«غير المتزايدة». إن كانت المسألة تسمح بتكرار القيم المتساوية (مثل 5, 5, 3)، فاستبدل شرط a[j] > a[i] بالشرط a[j] >= a[i]. اقرأ نص السؤال بدقة، لأن اختبارًا واحدًا يحوي قيمًا متساوية قد يكشف هذا الخلط ويُسقط حلّك.

نصيحة إضافية: إن طُلب منك استرجاع المتتالية نفسها لا طولها فقط، احتفظ بمصفوفة «آباء» تسجّل عند كل عنصر مؤشرَ العنصر السابق الذي وسّعنا منه، ثم تتبّعها عكسيًا من موضع أكبر قيمة في dp.

الأسئلة الشائعة

هل LDS تعني دائمًا أطول متتالية فرعية متناقصة؟ في سياق الخوارزميات وهياكل البيانات، نعم هذا هو المعنى المتداول. لكن الاختصار نفسه يُستعمل في مجالات أخرى بمعانٍ مختلفة تمامًا، لذا احكم دائمًا من السياق.

ما الفرق بين LDS وLCS؟ LCS تعني «أطول متتالية فرعية مشتركة» بين سلسلتين، وهي مسألة مختلفة تتعامل مع مدخلين اثنين، بينما LDS تعمل على مصفوفة واحدة وتبحث عن الترتيب التنازلي داخلها.

هل يمكن حلها بأسرع من O(n²)؟ نعم، بزمن O(n log n) عبر تحويلها إلى مسألة LIS على المصفوفة المعكوسة واستخدام البحث الثنائي مع مصفوفة الأطراف.

ماذا لو كانت كل عناصر المصفوفة متزايدة؟ عندها يكون طول أطول متتالية متناقصة هو 1 فقط، لأنه لا يوجد أي زوج يسير تنازليًا، وكل عنصر منفرد يُعدّ متتالية طولها واحد.