أكبر مجموع مقطع متصل غير فارغ: حالة النهاية وحدود الشاهد

مقطع متصل غير فارغ وهدف مجموع

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

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

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

[1]

ست قيم موجبة وسالبة

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

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

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

الشاهد من واحد إلى ما قبل أربعة

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

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

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

حالة أفضل مجموع ينتهي هنا

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

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

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

مد السابق أو بدء عنصر جديد

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

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

في الخطوة الأولى بعد سالب 2، نراجع العنصر 3. المد يعطي واحدًا، والعنصر وحده يعطي ثلاثة، فنبدأ عند موضع واحد. ثم عند سالب 1 يعطي المد اثنين، وهو أفضل من سالب 1 وحدها، فنحتفظ بالبداية. وعند 3 التالية يصير المد خمسة، فيتحسن الأفضل العام ونحفظ حدوده.

جدول النهاية والأفضل العام

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

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

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

الأفضل العام يحفظ الحدود عند التحسن

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

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

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

جميع القيم السالبة لا تعطي صفرًا هنا

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

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

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

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

التعادل وسياسة الشاهد

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

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

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

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

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

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

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

def maximum_segment(values):
    data = tuple(values)
    if not data:
        raise ValueError("nonempty input required")
    if any(type(value) is not int for value in data):
        raise TypeError("integer values required")
    current = best = data[0]
    current_start = best_start = 0
    best_stop = 1
    trace = [{"position": 0, "ending_sum": current, "best_sum": best}]
    for position in range(1, len(data)):
        extended = current + data[position]
        if extended < data[position]:
            current = data[position]
            current_start = position
        else:
            current = extended
        if current > best:
            best = current
            best_start = current_start
            best_stop = position + 1
        trace.append({"position": position, "ending_sum": current, "best_sum": best})
    return {"sum": best, "start": best_start, "stop": best_stop,
            "values": data[best_start:best_stop], "trace": tuple(trace)}

الفارغ والمنفرد والموجب

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

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

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

اختيار الموجبات أو أكبر متوسط سؤال آخر

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

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

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

مرجع كل النطاقات غير الفارغة

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

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

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

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

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

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

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