أطول تتابع جزئي متزايد: ترتيب الفهارس واستعادة شاهد دون اشتراط التجاور

قيمة تزداد وفهرس يحفظ الأصل

نريد اختيار عناصر من تتابع عددي مع الحفاظ على ترتيب ظهورها الأصلي، بحيث تكون كل قيمة مختارة أكبر من السابقة. يوضح مرجع CP-Algorithms الشرطين معًا: فهارس متزايدة وقيم متزايدة تزايدًا صارمًا. ويصف تعريف NIST التتابع الجزئي بأنه ينتج من حذف عناصر دون اشتراط أن يكون مقطعًا متجاورًا. سنطبق هذه الفكرة على أعداد مؤلفة ونحفظ الفهارس مع القيم.

الحفاظ على ترتيب الأصل لا يلزم اختيار كل عنصر. يمكن تجاوز قيمة لا تلائم التزايد، لكن لا يجوز العودة إلى موضع سبق موضعًا اخترناه. إذا أعطتنا طريقة قيمًا مرتبة بعد فرز كامل القائمة، فقد غيرت ترتيب الأصل بدل اختيار جزء منه. لذلك نراجع شرط الفهارس منفصلًا من شرط القيم، حتى لا تخفي قائمة تصاعدية صحيحة مخالفةً لترتيب الإدخال.

التزايد هنا صارم، فلا نضم قيمة مساوية إلى سابقتها. وقد يكون سؤال آخر عن تتابع غير متناقص يسمح بالمساواة، لكنه يحتاج عقدًا آخر. الأعداد تعليمية صحيحة بلا قياسات خارجية، ولا نستنتج منها اتجاهًا اقتصاديًا أو أداءً لنموذج. المطلوب أطول عدد عناصر يحقق الشرطين المعلنين في التتابع نفسه.

[1] [2]

ست قيم مرتبة كما دخلت

الإدخال الأصلي من الموضع صفر إلى خمسة هو 3 ثم 1 ثم 2 ثم 0 ثم 5 ثم 4. لا نفرز هذه القيم قبل اختيار الشاهد. نستطيع أخذ 1 عند الموضع واحد، ثم 2 عند اثنين، ثم 5 عند أربعة، فنحصل على قيم متزايدة بطول ثلاثة. الفهارس واحد واثنان وأربعة تتزايد أيضًا وتحدد أي ظهور اخترناه.

القيمة 0 عند الموضع ثلاثة لم تدخل الشاهد، لأنها تأتي بعد 2 بقيمة أصغر منه. هذا لا يمنعها من بدء تتابع جديد في حالة أخرى؛ يمكن أخذ 0 ثم 5، مثلًا، لكن طولهما اثنان. والقيمة 3 الأولى لا يمكن أن تسبق 1 ثم 2 في شاهد صارم متزايد، لأن القيمتين أصغر منها رغم أن موضعيهما متأخران.

يعرض الرسم الرئيسي كل موضع وقيمته وطول أفضل تتابع ينتهي فيه، ثم يبرز الفهارس التي استعادها كودنا. نحتفظ بالقيم غير المختارة في الصورة بدل حذفها من عرض الأصل، حتى تظهر الفجوة عند الموضع ثلاثة. الأعداد والهويات الموضعية من تأليف المثال، ولا تمثل بيانات سلسلة زمنية أو تجربة حقيقية لم نقرأها.

الفهارس تتجاوز موضعًا ولا تعكس الترتيب

الفهارس واحد واثنان وأربعة تختار عناصر وفق تسلسلها الأصلي، لكنها تتخطى الموضع ثلاثة. لذلك الشاهد 1 ثم 2 ثم 5 ليس مقطعًا متجاورًا في القائمة الأصلية. لو اشترطنا التجاور، لما جاز تجاوز الصفر بين 2 و5. هذا فرق في المسألة نفسها، وليس وصفًا شكليًا لطريقة طباعة النتائج.

في المقابل، أخذ القيمة 0 ثم 1 ثم 2 من الأصل يحتاج الفهارس ثلاثة ثم واحد ثم اثنين، وهي لا تتزايد. القيم مرتبة تصاعديًا، لكنها ليست شاهدًا صحيحًا لعقدنا بهذا الاختيار. فحص القيمة وحدها قد يقبل هذا الترتيب الخاطئ، ولهذا ترجع الدالة الفهارس إلى جانب القيم لا قائمة الأعداد فقط.

ونشترط أيضًا ألا نكرر الموضع نفسه كي نطيل الشاهد. الانتقال دائمًا من موضع أسبق إلى موضع لاحق، فيحفظ كل ظهور مرة واحدة. إذا تكررت قيمة في مواضع متعددة، يكون لكل ظهور فهرس مستقل، لكن شرط التزايد الصارم يقرر هل يمكن ضمه بعد سابق محدد. لا نخلط هوية الموضع بمساواة القيمة التي يحملها.

الحالة أطول تتابع ينتهي هنا

نعرّف خانة الحالة عند الموضع i بأنها طول أطول تتابع متزايد ينتهي تحديدًا بعنصر ذلك الموضع. ليست هذه الخانة طول الأفضل في كل ما سبق، وليست قيمة العنصر نفسه. يمكن لعنصر صغير متأخر أن يملك حالة بطول واحد رغم وجود شاهد أطول ينتهي في موضع سابق، لأننا اشترطنا أن تكون نهايته الحالية جزءًا من الشاهد.

في أصلنا، القيمة 0 عند الموضع ثلاثة لا تجد قبلها قيمة أصغر من صفر، فحالتها واحد. لكن قبل الوصول إليها كان التتابع 1 ثم 2 موجودًا بطول اثنين. لذلك حالة الموضع ثلاثة لا تخبرنا أن أفضل تتابع في بادئة القائمة صار واحدًا؛ تخبرنا أن أفضل ما ينتهي عند هذه القيمة نفسها هو عنصرها المفرد.

بعد حساب الحالات لكل المواضع، نأخذ أكبر طول بينها ونحفظ الموضع الذي حققه. لا نستعمل الخانة الأخيرة وحدها جوابًا عامًّا دون مراجعة معناها. في مثال مستقل 1 ثم 2 ثم 3 ثم 0، تكون الحالات 1 و2 و3 و1، بينما الجواب العام ثلاثة، لا الواحد الذي يظهر عند نهاية القائمة.

مرشح من موضع أسبق وقيمة أصغر

نبدأ حالة كل موضع غير فارغ بطول واحد، لأن العنصر نفسه شاهد صالح مفرد. ثم نراجع كل موضع j أسبق منه، فإذا كانت قيمته أصغر من القيمة الحالية، يمكن مد أفضل تتابع ينتهي عند j بإضافة العنصر الحالي. طول المرشح هو حالة j زائد واحد. نحتفظ بالمرشح الذي يزيد الطول المسجل، ونحفظ j سابقًا لاستعادة الطريق لاحقًا.

لماذا تكفي حالة الأفضل عند j؟ أي شاهد ينتهي بالعنصر الحالي وله عنصر قبله ينتهي ببعض j الذي يحقق الشرطين. إذا كانت مقدمته إلى j أقصر من أفضل مقدمة نعرفها إليه، نستطيع استعمال الأفضل ثم إلحاق القيمة الحالية. لا نغير موضع j أو قيمته، ولذلك يبقى الانتقال إليه ومنه صالحًا ضمن هذا العقد.

وعند موضع خمسة ذي القيمة 4، لا يمكن أن نمد الشاهد المنتهي بالقيمة 5 عند أربعة، لأنها ليست أصغر من 4. لكن يمكن أن نمد الشاهد 1 ثم 2 المنتهي عند اثنين، فيصبح 1 ثم 2 ثم 4 بطول ثلاثة. مراجعة الفهرس وحدها كانت ستسمح بالسابق أربعة؛ مراجعة القيمة معها تستبعده وتبقي المرشح المناسب.

جدول واحد وواحد واثنين وواحد وثلاثة وثلاثة

الحالة عند القيمة 3 الأولى واحد، وعند 1 التالية واحد أيضًا، لأنها لا تجد قيمة أصغر قبلها. عند القيمة 2 نستفيد من 1 السابقة فتكون الحالة اثنين. عند الصفر تعود الحالة واحدًا، ثم عند 5 نستطيع مد شاهد 1 ثم 2 إلى طول ثلاثة. وعند 4 نجد شاهدًا بالطول نفسه ينتهي بالقيمة 4.

إذن الجدول من الموضع صفر إلى خمسة هو 1 ثم 1 ثم 2 ثم 1 ثم 3 ثم 3. لا يلزم أن يصعد الجدول مع الفهارس أو أن تكون القيمة الأكبر صاحبة شاهد أطول في كل قائمة. معنى كل خانة مرتبط بما يمكن أن ينتهي عند موضعها، ثم نبحث عن أكبر حالة على مستوى جميع النهايات الممكنة.

يمكننا التحقق من الأعداد الصغيرة يدويًا ثم مقارنة الجدول بمرجع مستقل. كما نراجع أن الطول العام ثلاثة له شاهد صالح، وأن البحث في جميع اختيارات الفهارس الصغيرة لا يجد شاهدًا بطول أربعة في أصلنا. صلاحية 1 ثم 2 ثم 5 تثبت حدًا يبلغ ثلاثة، لكنها وحدها لا تثبت غياب شاهد أكبر؛ نحتاج العلاقة الصحيحة أو تحققًا مناسبًا من الأمثلية.

السابق واستعادة واحد ثم اثنين ثم خمسة

في سياسة كودنا تبقى النهاية عند الموضع أربعة، لأن حالتها ثلاثة ظهرت قبل حالة الموضع خمسة المتعادلة معها. السابق المحفوظ لأربعة هو اثنان، والسابق لاثنين هو واحد، ثم لا سابق للموضع واحد في هذا الشاهد. نتبع هذه الفهارس بالرجوع، فنقرأ أربعة ثم اثنين ثم واحدًا، ونعكسها لنعرض واحدًا ثم اثنين ثم أربعة.

باختيار القيم من الأصل بهذه الفهارس نحصل على 1 ثم 2 ثم 5. طول قائمة الفهارس ثلاثة، وطول القيم ثلاثة، وكلاهما يوافق النتيجة العامة. نراجع أيضًا أن كل قيمة تطابق موضعها الأصلي وأن العلاقات المتتالية صارمة. لا نعيد بناء شاهد بإضافة واحد إلى طول الحالة ثم تخمين قيم لم نحفظ وسيلة ربطها بالأصل.

تقل الفهارس في كل خطوة رجوع لأن السابق جاء من موضع أقدم. لذلك تنتهي السلسلة عند حالة مفردة بلا سابق، ولا نحتاج مسارًا دائريًا أو تكرار موضع. الحقول محفوظة لنسخة الإدخال التي حسبناها؛ تغيير القائمة أو ترتيبها بعد ذلك لا يجعل السوابق القديمة تشير تلقائيًا إلى العناصر المقصودة في نسخة جديدة.

شاهد آخر بالطول نفسه

الفهارس واحد واثنان وخمسة تعطي القيم 1 ثم 2 ثم 4، وهي شاهد صحيح آخر بطول ثلاثة. لم يعرضه كودنا لأن النهاية عند الموضع أربعة احتفظت بالأولوية حين تعادل الطول العام. لا يعني ذلك أن القيمة 4 لا تصلح لنهاية حل أمثل، بل يعني أن الدالة ترجع شاهدًا واحدًا وفق سياسة محددة داخل مرورها.

وعند تعادل مرشحين لحالة واحدة لا تستبدل الدالة السابق المحفوظ إلا إذا زاد الطول. لذلك قد تتغير هوية شاهد مع سياسة أخرى للتعادل دون تغيير الجواب العددي. لا نطلب من كل تنفيذ أن يطبع القيم نفسها إذا كان العقد يطلب أي شاهد أطول صالح، لكننا نراجع فهارسه وقيمه وطوله حتى لا نخفي خطأ تحت عبارة البدائل متعددة.

ولا نسمي الشاهد المعروض أصغر شاهد أبجديًا أو أقل قيمة نهاية في كل حالة، لأننا لم ننفذ هذين الهدفين. كما لا نقلل مجموع القيم أو نزيده. في مثال 100 ثم 1 ثم 2 ثم 3 يكون الشاهد الأطول 1 ثم 2 ثم 3، بينما القيمة 100 المفردة أكبر مجموعًا منه. هدف العدد مختلف من هدف مجموع القيم.

تكرار القيمة يفرق الصارم من غير المتناقص

في الإدخال 2 ثم 2 ثم 2، لا نستطيع اختيار عنصرين متتاليين في شاهد متزايد تزايدًا صارمًا، لأن القيمة الثانية ليست أكبر من الأولى. لذلك الطول الأمثل واحد في عقدنا، ويحفظ كودنا الموضع صفر شاهدًا مفردًا. اختلاف مواضع الظهور لا يغير مساواة القيم التي دخلت شرط المقارنة.

أما إذا طلبنا تتابعًا غير متناقص، يمكن أن يكون الشاهد 2 ثم 2 ثم 2 بطول ثلاثة، لأن المساواة أصبحت مسموحة. هذا سؤال آخر يحتاج تغييرًا صريحًا للشرط والاختبارات. لا نكتب أن كلمة متزايد وحدها تكفي لتعريف كيفية التعامل مع التعادل، خاصةً في بيانات تحوي أعدادًا متكررة كثيرة.

ونراجع المثال المتكرر قبل الاعتماد على قائمة كلها قيم مختلفة، لأن المختلفات قد لا تكشف فرق أصغر من وأصغر أو مساوٍ في الكود. يظل ترتيب الفهارس ضروريًا في الحالتين؛ السماح بتساوي القيم لا يسمح بالعودة إلى موضع سابق أو باستعمال الموضع نفسه عدة مرات كي نصنع طولًا أكبر من الإدخال.

الكود الأصلي وعقد المدخل

الدالة التالية تقبل تتابعًا من أعداد int العادية، وتحفظ نسخة tuple منه للحساب. ترفض bool والعشري والنص بدل تحويلها ضمنيًا إلى قيم مقارنة. هذه حدود تنفيذ تعليمي محدد، وليست ادعاءً أن مسألة التتابع لا يمكن تعريفها على أنواع أخرى لها ترتيب مناسب وعقد معلن.

ترجع الدالة أربعة حقول: الطول العام، وفهارس الشاهد، وقيمه، وجدول أطوال الحالات المنتهية عند كل موضع. لا تفرز الإدخال، ولا ترجع فهارس مصفوفة أخرى. يبدأ كل موضع غير فارغ بحالة مفردة، ثم يراجع المواضع الأسبق ويحدث الطول والسابق عند تحسن حقيقي، ويحفظ نهاية أولى للطول الأكبر حين يتعادل لاحقًا.

هذه طريقة موثقة في المرجع الذي قرأناه، لكن الكود هنا صياغة أصلية لعقدنا ومخرج يجمع الحقول التي نراجعها. لا نزعم اختراع خوارزمية جديدة أو تنفيذ النسخ الأسرع التي يناقشها المصدر. أمثلتنا ورسومنا ومرجع الفحص من إعداد المقال، ولا نعيد استخدام سلسلة أعداد المصدر أو صورته بوصفها بيانات أصلية لنا.

def increasing_witness(values):
    data = tuple(values)
    if any(type(value) is not int for value in data):
        raise TypeError("integer sequence required")
    if not data:
        return {"length": 0, "indices": (), "values": (), "ending_lengths": ()}
    lengths = [1] * len(data)
    previous = [None] * len(data)
    endpoint = 0
    for position in range(len(data)):
        for earlier in range(position):
            if data[earlier] < data[position]:
                candidate = lengths[earlier] + 1
                if candidate > lengths[position]:
                    lengths[position] = candidate
                    previous[position] = earlier
        if lengths[position] > lengths[endpoint]:
            endpoint = position
    indices = []
    current = endpoint
    while current is not None:
        indices.append(current)
        current = previous[current]
    indices.reverse()
    return {
        "length": len(indices),
        "indices": tuple(indices),
        "values": tuple(data[index] for index in indices),
        "ending_lengths": tuple(lengths),
    }

لماذا لا نفرز الأصل بدل الاختيار؟

إذا فرزنا أصلنا تصاعديًا نحصل على 0 ثم 1 ثم 2 ثم 3 ثم 4 ثم 5. القيم الست متزايدة، لكن فهارسها في الأصل هي ثلاثة ثم واحد ثم اثنان ثم صفر ثم خمسة ثم أربعة، وهي لا تتزايد. لذلك هذه القائمة المرتبة ليست شاهدًا بطول ستة لمسألتنا، بل ترتيب جديد أنشأناه بتغيير علاقات الظهور.

الفرز قد يفيد سؤالًا عن ترتيب القيم كلها، لكنه لا يحافظ تلقائيًا على القيد الذي جعلنا نختار جزءًا من أصل معلوم. حتى إزالة المكررات بعد الفرز لا تصلح هذا الفرق، لأن أصلنا أصلًا ذو قيم مختلفة. المشكلة ترتيب الفهارس، لا وجود قيم متعادلة نحتاج التخلص منها.

يمكن للقارئ فحص أي شاهد مزعوم بالرجوع إلى مواضعه الأصلية. فإذا اضطر للانتقال من الموضع ثلاثة إلى واحد، خالف عقد الاختيار، رغم أن القيم زادت. ولهذا نربط النتيجة بنسخة الأصل وفهارسها، ونفصل مهمة بناء ترتيب جديد من مهمة إيجاد أطول اختيار يظل داخل ترتيب المصدر نفسه.

عرض الرسم بالحجم الكامل

الفارغ والمنفرد والمتناقص

الإدخال الفارغ يعطي طولًا صفرًا وفهارس وقيمًا وجدول حالات فارغة في دالتنا. لا نخترع حالة بطول واحد دون عنصر يحققها. أما سجل عددي واحد فيعطي شاهدًا مفردًا وطولًا واحدًا، لأن شرط الزيادة بين عنصرين لا يحتاج مقارنة حين لا توجد إلا قيمة واحدة.

وفي إدخال متناقص مثل 5 ثم 4 ثم 3، لا يمكن مد عنصر أسبق بقيمة أصغر، فيبقى الطول واحدًا في كل موضع ويختار الكود النهاية الأولى. هذا لا يعني أنه بحث عن أقل قيمة منفردة؛ الشاهد قد يكون 5 وفق سياسته. ينبغي أن نقرأ هوية الشاهد من القرار الفعلي لا من تخمين أن الإجابة المثلى لازم أن تبدأ بأصغر قيمة.

كما نقبل أعدادًا سالبة وصفرًا وفق ترتيبها العددي. مثلًا سالب 2 ثم صفر ثم 3 شاهد صارم متزايد بطول ثلاثة. لا نعتبر الصفر علامة غياب ولا نحذف السالب كي نجعل الجدول أسهل. نوع المقارنة والقيم المسموحة جزء من المدخل، وتغييرهما يقتضي مراجعة النتائج والاختبارات من جديد.

مرجع كل مجموعات الفهارس

للتحقق المستقل، نجرب كل مجموعة فهارس صغيرة في ترتيبها الأصلي، ونستخرج القيم الموافقة لها. نراجع هل تزيد القيم زيادة صارمة، ثم نحفظ أكبر طول بين الاختيارات الصالحة. هذا المرجع لا يستخدم جدول الحالات أو سوابق الدالة، فيستطيع كشف طول خاطئ نتج من تمديد قيمة لا تصلح أو من قبول مساواة لم نسمح بها.

نفذنا المقارنة على تتابعات بأطوال من صفر إلى سبعة وقيم من سالب 1 وصفر و2. ونراجع الشاهد نفسه: فهارسه تتزايد، وقيمه توافق الأصل في تلك الفهارس، وعددها يساوي الطول، والقيم المتتالية تزيد فعلًا. لا يكفي تطابق طول مع مرجع إذا كانت الفهارس تشير إلى عناصر أخرى أو الشاهد لا يحترم علاقة المقارنة.

نضيف أصلنا ذي ست قيم، والشاهد البديل، والمتكرر، والمتناقص، والفارغ، وأنواع المدخل المرفوضة. كما نراجع حالة أن الخانة الأخيرة أصغر من أفضل طول عام. هذه فحوص محدودة مستقلة، وليست إعلانًا أن كل امتداد إلى أوزان أو أنواع خاصة أو سياسة تعادل مختلفة تحقق بهذه النسخة دون مراجعة عقدها.

بطاقة النتيجة وكلفة مراجعة الأزواج

يمكن وصف النتيجة ببطاقة: الأصل 3 ثم 1 ثم 2 ثم 0 ثم 5 ثم 4، والتزايد صارم، والفهارس تبدأ من صفر ولا يشترط تجاورها. نكتب جدول النهايات 1 و1 و2 و1 و3 و3، والطول العام ثلاثة، والفهارس واحد واثنان وأربعة، والقيم 1 و2 و5. نذكر أن هذا شاهد واحد وأن هناك بديلًا بالطول نفسه.

في التنفيذ نراجع المواضع السابقة لكل موضع، ولذلك يكبر عدد الأزواج المرشحة عندما يكبر الإدخال. كما نحفظ أطوالًا وسوابق وقيمًا تتعلق بعدد العناصر. لم نقس زمنًا على ملفات كبيرة، ولا ندعي أن طريقة تربيعية تعليمية هي أسرع نسخة ممكنة أو أنها تنفذ حيلة أخرى من المصدر لم تدخل الكود.

قبل اعتماد شاهد، راجع ترتيب الأصل وصرامة المقارنة ومعنى كل خانة وموضعها. ثم تحقق من الفهارس والقيم والطول معًا، ولا تستبدل الاختيار بفرز يغير المصدر. ستعرف بذلك ما حسبناه: أطول تتابع جزئي بشاهد قابل لإعادة الفحص، دون ادعاء تجاور أو فرادة أو ترتيب عددي جديد لم يكن ضمن السؤال.