Split Array Largest Sum

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

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

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

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

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

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

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

+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] مبلغ 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.

سؤال إضافي

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

تلميحات

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

فُتح 0 من 3

الحل

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

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

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

الفكرة

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

يصل عدد خطوات التنفيذ إلى k·n²/2: أي نحو 1.8 × 10^10 عندما تكون n = 5000 وk = 2500.

الخوارزمية

أنشئ 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، تحرّك من اليسار إلى اليمين وأضف القيم إلى الجزء الحالي ما دام مجموعها لا يتجاوز c، ثم ابدأ جزءًا جديدًا. بهذه الطريقة تحصل على أقل عدد ممكن من الأجزاء. وبالمقارنة مع أي تقسيم صالح، ينتهي الجزء الأول في الطريقة الجشعة عند موضع أبعد إلى اليمين على الأقل، لذا يبدأ جزؤها التالي عند موضع يساوي موضع الجزء الآخر أو يتجاوزه. والقيم التي تضمّها حتى نهاية ذلك الجزء هي مقطع من جزء يفي بالشرط، ومع عدم وجود قيم سالبة، لا يتجاوز مجموع المقطع مجموع الجزء بأكمله. لذا لا تتأخر الطريقة الجشعة أبدًا.

استخدام أقل من k أجزاء لا يقل جودة عن استخدام k أجزاء: فتقسيم جزء يحتوي على قيمتين أو أكثر إلى جزأين لا يزيد أيًّا من المجموعين. لذا يكون الاختبار هو partsNeeded(c) ≤ k.

استخدم البحث الثنائي لإيجاد أصغر حدّ ينجح، بين max(nums)، لأن هذه القيمة تقع ضمن أحد الأجزاء، وsum(nums)، التي تكفي دائمًا لجزء واحد.

الخوارزمية

عيّن 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. بالنسبة إلى [3, 0, 4] وk = 3، يقسم الحد 4 القيم إلى [3, 0] و[4]، لذا لا ينجح أي حد.
بدء عدّ الأجزاء من 0، ما يجعل كل عدد أقل بواحد.
تعيين hi = mid - 1 عندما تكون mid مناسبة، ما يؤدي إلى فقدان الإجابة عندما تكون mid.
بدء i في البرمجة الديناميكية (DP) من 0. تُقرأ قيمة الخلية التي تحتوي على عدد من القيم أقل من عدد الأجزاء على أنها تكلفة 0، لذا تعطي [100, 1, 1] مع k = 3 النتيجة 2 بدلًا من 100.

أسئلة شائعة3

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

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

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

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

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

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

def splitArray(nums, k):
    # اكتب الشيفرة هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

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

الإخراج المتوقع