Split Array Largest Sum

Q: ما هو التعقيد الزمني لمسألة تقسيم المصفوفة لتصغير أكبر مجموع؟

يعمل البحث الثنائي في زمن O(n log S) ، حيث إن n هو طول nums و S هو مجموعها. كل فحص جشع هو مرور واحد على المصفوفة، ويتقلص نطاق الحدود إلى النصف بعد كل فحص: نحو 29 فحصًا عندما تكون S = 5 × 10^8 . ويستخدم مساحة إضافية O(1) . أما البرمجة الديناميكية فتستغرق زمنًا O(k·n²) وتستخدم مساحة O(n) .

Q: لماذا يكون فحص إمكانية التنفيذ رتيبًا؟

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

Q: لماذا يعثر الفحص الجشع على أقل عدد من الأجزاء؟

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

Q: هل يعمل البحث الثنائي مع الأعداد السالبة؟

لا. مع القيم السالبة، قد تؤدي إضافة قيمة إلى خفض المجموع، لذا قد تُنهي الخوارزمية الجشعة جزءًا مبكرًا وتفوّت تقسيمًا ناجحًا. وقد يؤدي تقسيم جزء أيضًا إلى رفع مجموع أحد الجزأين فوق مجموع الجزء كاملًا، لذا لم يعد وجود أقل من k أجزاء يعني أن التقسيم إلى k أجزاء سينجح. لا تفترض البرمجة الديناميكية أيًا من ذلك، وتظل صحيحة، بزمن O(k·n²) .

صعبالبحث الثنائي البرمجة الديناميكية

+10

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

أعِدّ أقل تكلفة يمكن الوصول إليها عند التقسيم إلى k أجزاء.

الدالة

splitArray(nums: integer-array, k: integer) → integer

numsinteger-array: القيم غير السالبة، بالترتيب
kinteger: عدد الأجزاء المتجاورة التي يجب تقطيعها إليها
تُرجعinteger: أصغر قيمة ممكنة لمجموع الجزء الأكبر

القيود

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length
يحتوي كل جزء على قيمة واحدة على الأقل. ومجموع قيم الجزء الذي تكون جميع قيمه 0 هو 0، وهذا مسموح به.

أمثلة

المدخلات: nums = [6, 2, 9, 4, 7, 3]k = 3
المخرجات: 13
الشرح: التقسيم [6, 2]، [9, 4]، [7, 3] مجموع أجزائه هو 8 و13 و10، لذا تكلفته 13. لا يوجد تقسيم تكلفته 12: فتعبئة الأجزاء من اليسار إلى اليمين بحيث لا يتجاوز مجموع كل جزء 12 تعطينا [6, 2]، [9]، [4, 7]، [3]، أي أربعة أجزاء بينما المسموح ثلاثة فقط.

المدخلات: nums = [8, 1, 1, 1, 5]k = 2
المخرجات: 8
الشرح: العدد 8 موجود في أحد الأجزاء، لذا لا يمكن أن تكون كلفة أي تقسيم أقل من 8. ومجموع كلٍّ من [8] و[1, 1, 1, 5] يساوي 8، لذا تم بلوغ 8.

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

سؤال إضافي

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

تلميحات

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

فُتح 0 من 3

الحل

يتعارض المطلبان معًا: يجب أن تستخدم k أجزاء بالضبط، وتريد أن يكون أكبر جزء صغيرًا قدر الإمكان. إن تجربة كل موضع للقطع k-1 تؤدي إلى انفجار عدد الاحتمالات، ويقلّص ذلك برنامج ديناميكي على البادئات إلى O(k·n²)، لكنه يظل بطيئًا جدًا لـ 5000 قيمة. تقلب الفكرة السريعة السؤال رأسًا على عقب. فبدلًا من البحث عن أفضل تقسيم، خمن حدًا أقصى واسأل ما إذا كان بالإمكان إبقاء k أجزاء ضمنه. تجيب جولة جشعة واحدة عن ذلك، ولا تتغير الإجابات إلا مرة واحدة مع ازدياد الحد الأقصى، ويعثر البحث الثنائي على نقطة التغير في نحو 29 جولة.

البرمجة الديناميكية على البوادئ

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

انظر إلى الجزء الأخير من التقسيم. إذا كانت أول j قيمة تكوّن p أجزاء، فالجزء الأخير هو مقطع ما nums[i..j-1]، وأول i قيمة تكوّن الأجزاء p-1 الأخرى. التكلفة هي الأكبر من عددين: تكلفة تلك الأجزاء p-1، ومجموع المقطع الأخير. أيًّا كان المقطع الأخير، فأنت تريد تقسيم أول i قيمة بأقل تكلفة ممكنة، وهذا التقسيم الأمثل لا يعتمد على أي شيء يقع إلى يمينه. لذا يمكنك حسابه مرة واحدة وإعادة استخدامه.

اكتب best[p][j] للدلالة على أقل تكلفة لتقسيم أول j قيمة إلى p أجزاء. لا يوجد خيار عند وجود جزء واحد: best[1][j] هو مجموع أول j قيمة. عند وجود أجزاء أكثر، جرّب كل بداية i للجزء الأخير: best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i])، حيث إن prefix[j] هو مجموع أول j قيمة. تبدأ قيمة i من p-1، لأن الأجزاء غير الفارغة p-1 تحتاج إلى p-1 قيمة على الأقل، وتمتد حتى j-1، لأن الجزء الأخير يحتاج إلى قيمة واحدة. الإجابة هي best[k][n]. الصف p لا يقرأ إلا الصف p-1، لذا يكفي صفّان طول كل منهما n+1.

في المثال الأول، يمكن أن ينتهي الجزء الأول بعد 6 (التكلفة max(6, 15) = 15)، أو بعد 2 (max(8, 13) = 13)، أو بعد 9 (max(17, 4) = 17)، عند تقسيم [6, 2, 9, 4] إلى جزأين، لذا فإن best[2][4] = 13. ثم تجرّب best[3][6] الجزء الأخير [7, 3]، فتحصل على max(13, 10) = 13، ولا تتفوق أي بداية أخرى على هذه النتيجة.

المشكلة تكمن في مقدار العمل. هناك k صفوف، وn نهايات لكل صف، وما يصل إلى n بداية لكل نهاية: أي ما يصل إلى k·n²/2 خطوة. عندما يكون n = 5000 وk = 2500، تُنفَّذ الحلقة الداخلية نحو 1.8 × 10^10 مرة: أي 18 ثانية حتى عند تنفيذ 10^9 خطوة بسيطة في الثانية. تظل البرمجة الديناميكية جديرة بالمعرفة: فهي لا تفترض أبدًا أن القيم غير سالبة، لذا تظل فعّالة في الحالات التي لا تنجح فيها الطريقة السريعة.

الخوارزمية

أنشئ prefix، حيث تمثل prefix[j] مجموع أول j من القيم.
عيّن صف الجزء الواحد: best[j] = prefix[j].
لكل عدد أجزاء p من 2 إلى k، ولكل نهاية j من p إلى n، خذ القيمة الصغرى على i من p-1 إلى j-1 للتعبير max(best[i], prefix[j] - prefix[i]).
خزّن تلك القيم الصغرى في صف جديد واجعله best.
أعِد best[n].

def splitArray(nums, k):
    n = len(nums)
    # prefix[j] is the sum of the first j values
    prefix = [0] * (n + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    # best[j]: the smallest largest part when the first j values form one part
    best = prefix[:]
    for parts in range(2, k + 1):
        nxt = [0] * (n + 1)
        for j in range(parts, n + 1):
            lowest = prefix[j]  # never worse than one part holding everything
            for i in range(parts - 1, j):
                # the first i values form parts-1 parts, nums[i..j-1] is the last part
                worst = max(best[i], prefix[j] - prefix[i])
                if worst < lowest:
                    lowest = worst
            nxt[j] = lowest
        best = nxt
    return best[n]

البحث الثنائي عن أكبر مجموع

الفكرة

اعكس السؤال. اختر حدًا أقصى c واسأل: هل يمكن تقسيم nums إلى k أجزاء بحيث لا يتجاوز مجموع كل جزء c؟ إجابة المسألة هي أصغر حد أقصى تكون الإجابة عنده نعم. هذا السؤال أسهل بكثير من المسألة الأصلية، لسببين.

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

ثانيًا، عدد أجزاء أقل من k يفي بالغرض مثل العدد k تمامًا. إذا احتاجت الطريقة الجشعة إلى m < k أجزاء، فقسّم جزءًا يحتوي على قيمتين أو أكثر إلى جزأين. مجموع الجزأين لا يتجاوز مجموع الجزء كله، لأنه لا توجد قيمة سالبة، وبما أن n ≥ k، فهناك دائمًا جزء كهذا إلى أن تصل إلى k. لذا يكون الاختبار partsNeeded(c) ≤ k.

والآن الخاصية الأساسية: الاختبار رتيب. إذا كان الحد الأقصى c ينجح، فإن c+1 ينجح أيضًا، لأن التقسيم نفسه يظل ملائمًا لحد أقصى أكبر. ضمن الحدود من max(nums) إلى sum(nums)، تكون الإجابات: لا، لا، ...، لا، نعم، نعم، ...، نعم، والمطلوب هو أول نعم. النطاق آمن عند طرفيه: لا يمكن لأي حد أقصى أقل من max(nums) أن يستوعب تلك القيمة، والمجموع الكلي يلائم دائمًا جزءًا واحدًا. وأول قيمة نعم هي أيضًا تكلفة فعلية، وليست مجرد حد: فإذا لم يكن مجموع أي جزء في تقسيمها مساويًا تمامًا لـ c، لنجح الحد الأقصى c-1 أيضًا.

تتبّع المثال الأول، [6, 2, 9, 4, 7, 3] مع k = 3. تتراوح الحدود القصوى من 9 إلى 31. عند الحد الأقصى 20، يكون التقسيم [6, 2, 9] و[4, 7, 3]: جزآن، نعم، فيصبح النطاق من 9 إلى 20. عند الحد الأقصى 14، يكون التقسيم [6, 2] و[9, 4] و[7, 3]: 3 أجزاء، نعم، فيصبح النطاق من 9 إلى 14. عند الحد الأقصى 11، يكون التقسيم [6, 2] و[9] و[4, 7] و[3]: 4 أجزاء، لا، فيصبح النطاق من 12 إلى 14. عند الحد الأقصى 13، يلزم 3 أجزاء، نعم، فيصبح النطاق من 12 إلى 13. عند الحد الأقصى 12، يلزم 4 أجزاء، لا، لذا فالإجابة هي 13.

تقرأ كل تمريرة n قيمة، وينخفض النطاق إلى النصف في كل مرة. مع مجموع S يصل إلى 5 × 10^8، يعني ذلك نحو 29 تمريرة على 5000 قيمة، أي قرابة 150000 خطوة.

الخوارزمية

اضبط lo = max(nums) وhi = sum(nums).
ما دام lo < hi، خذ mid = lo + (hi - lo) / 2.
احسب عدد الأجزاء التي تحتاج إليها الخوارزمية الجشعة تحت الحد mid: ابدأ بجزء واحد ومجموع جارٍ يساوي 0؛ وعندما تؤدي إضافة قيمة إلى تجاوز mid، أضف جزءًا وابدأ المجموع من جديد بتلك القيمة.
إذا كان العدد أقل من أو يساوي k، فاضبط hi = mid؛ وإلا فاضبط lo = mid + 1.
أعِد lo.

def splitArray(nums, k):
    def parts_needed(cap):
        # Fill each part left to right and start a new one only when the next value would pass cap.
        parts, current = 1, 0
        for x in nums:
            if current + x > cap:
                parts += 1
                current = x
            else:
                current += x
        return parts

    lo, hi = max(nums), sum(nums)  # one value per part at best, everything in one part at worst
    while lo < hi:
        mid = (lo + hi) // 2
        if parts_needed(mid) <= k:
            hi = mid  # mid works, so the answer is mid or smaller
        else:
            lo = mid + 1  # mid needs more than k parts, so the answer is larger
    return lo

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

البحث قصير، لذا تكمن الأخطاء في فحص الجشع وفي الحدود.

بدء lo بقيمة أقل من max(nums). يضع الفحص الجشع قيمةً أكبر من الحد الأقصى في جزء خاص بها ثم يواصل، لذلك يعتبر أن الحد الأقصى 5 مناسب لـ [1, 9] مع k = 2. ابدأ بأكبر قيمة، أو اجعل الفحص يفشل عندما تتجاوز قيمة واحدة الحد الأقصى.
اختبار partsNeeded(c) == k. غالبًا ما يحتاج الأسلوب الجشع إلى أجزاء أقل من k: بالنسبة إلى [3, 0, 4] وk = 3، يجمع الحد الأقصى 4 القيم في [3, 0] و[4]. مع == لن يجتاز أي حد أقصى الاختبار. يمكن دائمًا تقسيم الأجزاء الأقل عددًا إلى أجزاء أكثر، لذا اختبر ≤ k.
بدء عدّ الأجزاء من 0. يوجد الجزء الأول قبل أن تتجاوز أي قيمة سعته، لذا يبدأ العد من 1.
تعيين hi = mid - 1 عندما تنجح mid. قد يؤدي ذلك إلى تجاوز الإجابة نفسها. أبقِ hi = mid واجعل الحلقة تستمر ما دام lo < hi.
بدء i في البرمجة الديناميكية من 0. تمثل الخلية best[i] عندما يكون i < p-1 عددًا من القيم أقل من عدد الأجزاء، وهو ما لا يمكن لأي تقسيم تحقيقه، وفي صف مملوء بالأصفار تُقرأ تكلفتها على أنها 0. بالنسبة إلى [100, 1, 1] مع k = 3، تُخرج البرمجة الديناميكية عندها 2 بدلًا من 100. ابدأ i من p-1.
تجاوز الحدود عند القيم الأكبر. هنا المجموع لا يتجاوز 5 × 10^8، لذا تستوعبه الأعداد الصحيحة ذات 32 بت. إذا بلغت القيم 10^6، فإن 2148 قيمة منها تكفي لتجاوز 2^31-1، لذا استخدم مجاميع ذات 64 بت.

أسئلة شائعة4

ما هو التعقيد الزمني لمسألة تقسيم المصفوفة لتصغير أكبر مجموع؟

يعمل البحث الثنائي في زمن O(n log S)، حيث إن n هو طول nums وS هو مجموعها. كل فحص جشع هو مرور واحد على المصفوفة، ويتقلص نطاق الحدود إلى النصف بعد كل فحص: نحو 29 فحصًا عندما تكون S = 5 × 10^8. ويستخدم مساحة إضافية O(1). أما البرمجة الديناميكية فتستغرق زمنًا O(k·n²) وتستخدم مساحة O(n).

لماذا يكون فحص إمكانية التنفيذ رتيبًا؟

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

لماذا يعثر الفحص الجشع على أقل عدد من الأجزاء؟

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

هل يعمل البحث الثنائي مع الأعداد السالبة؟

لا. مع القيم السالبة، قد تؤدي إضافة قيمة إلى خفض المجموع، لذا قد تُنهي الخوارزمية الجشعة جزءًا مبكرًا وتفوّت تقسيمًا ناجحًا. وقد يؤدي تقسيم جزء أيضًا إلى رفع مجموع أحد الجزأين فوق مجموع الجزء كاملًا، لذا لم يعد وجود أقل من k أجزاء يعني أن التقسيم إلى k أجزاء سينجح. لا تفترض البرمجة الديناميكية أيًا من ذلك، وتظل صحيحة، بزمن O(k·n²).

Python

def splitArray(nums, k):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

nums = [6, 2, 9, 4, 7, 3]
k = 3

المتوقع