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: האם החיפוש הבינארי עובד עם מספרים שליליים?

לא. ערך שלילי יכול להקטין סכום, ולכן אלגוריתם חמדני עלול לסגור חלק מוקדם מדי, ופיצול של חלק יכול להעלות רכיב אחד מעל הסכום הכולל. ה-DP אינו מניח אף אחת מההנחות האלה ונשאר נכון.

קשהחיפוש בינארי תכנון דינמי

+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. לכן, ברגע שמגבלה מסוימת מתאימה, כל מגבלה גדולה יותר מתאימה גם היא, והתשובות יוצרות רצף של לא ולאחריו רצף של כן. חיפוש בינארי מוצא את התשובה החיובית הראשונה.

האם החיפוש הבינארי עובד עם מספרים שליליים?

לא. ערך שלילי יכול להקטין סכום, ולכן אלגוריתם חמדני עלול לסגור חלק מוקדם מדי, ופיצול של חלק יכול להעלות רכיב אחד מעל הסכום הכולל. ה-DP אינו מניח אף אחת מההנחות האלה ונשאר נכון.

def splitArray(nums, k):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

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

הפלט הצפוי