Split Array Largest Sum

Q: Jaka jest złożoność czasowa problemu Split Array Largest Sum?

O(n log S) czasu i O(1) dodatkowej pamięci, gdzie S jest sumą nums : każde zachłanne sprawdzenie wymaga jednego przejścia, a zakres limitów zmniejsza się o połowę po każdym sprawdzeniu. To około 29 sprawdzeń, gdy S = 5 × 10^8 . DP wymaga O(k·n²) czasu.

Q: Dlaczego sprawdzanie wykonalności jest monotoniczne?

Jeśli każda część podziału sumuje się do co najwyżej c , ten sam podział mieści się w limicie c+1 . Zatem gdy dany limit działa, każdy większy limit również działa, a odpowiedzi tworzą najpierw serię „nie”, a potem serię „tak”. Wyszukiwanie binarne znajduje pierwszą odpowiedź „tak”.

Q: Czy wyszukiwanie binarne działa z liczbami ujemnymi?

Nie. Wartość ujemna może obniżyć sumę, więc algorytm zachłanny może zamknąć część zbyt wcześnie, a podzielenie części może sprawić, że jeden fragment będzie większy od całości. DP nie zakłada żadnej z tych rzeczy i pozostaje poprawny.

TrudneWyszukiwanie binarne Programowanie dynamiczne

+10

Otrzymujesz tablicę nums nieujemnych liczb całkowitych oraz liczbę całkowitą k. Podziel nums dokładnie na k części, z których każda jest niepustym ciągiem sąsiadujących wartości, a części zachowują swoją kolejność. Każda część ma sumę, a kosztem podziału jest największa z tych sum.

Zwróć najmniejszy koszt, jaki można uzyskać, dzieląc tablicę na k części.

Funkcja

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

numsinteger-array: wartości nieujemne, w kolejności
kinteger: liczba sąsiadujących części, na które należy je podzielić
Zwracainteger: najmniejsza możliwa wartość sumy największej części

Ograniczenia

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length
Każda część zawiera co najmniej jedną wartość. Część, której wszystkie wartości wynoszą 0, sumuje się do 0, co jest dozwolone.

Przykłady

Wejście: nums = [6, 2, 9, 4, 7, 3]k = 3
Wyjście: 13
Wyjaśnienie: Podział [6, 2], [9, 4], [7, 3] kosztuje 13. Żaden podział nie kosztuje 12: pakowanie części od lewej do prawej przy limicie 12 daje [6, 2], [9], [4, 7], [3], czyli cztery części.

Wejście: nums = [8, 1, 1, 1, 5]k = 2
Wyjście: 8
Wyjaśnienie: 8 znajduje się w pewnej części, więc żaden podział nie może kosztować mniej niż 8. [8] i [1, 1, 1, 5] sumują się do 8.

Pytanie dodatkowe

Dzięki sumom prefiksowym zachłanne sprawdzenie może znaleźć, gdzie kończy się każda część, za pomocą wyszukiwania binarnego. Jak szybko działa cała metoda, gdy k jest małe?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Bezpośrednie szukanie najlepszego podziału kosztuje O(k·n²) nawet przy użyciu programowania dynamicznego. Odwróćmy pytanie: czy k części mogą zmieścić się poniżej danego limitu? Odpowiada na to jedno zachłanne przejście. Wraz ze wzrostem limitu odpowiedź zmienia się z „nie” na „tak” dokładnie raz, a wyszukiwanie binarne znajduje ten punkt.

Programowanie dynamiczne po prefiksach

Poprawne, ale nie kończy się na największych testach

Intuicja

Oznaczmy przez best[p][j] najmniejszy koszt podziału pierwszych j wartości na p części. Jeśli ostatnią częścią jest nums[i..j-1], koszt stanowi większa z wartości: best[p-1][i] oraz suma tej części, a najlepszy podział pierwszych i wartości nie zależy od niczego, co znajduje się na prawo od nich. Zatem best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), gdzie i przyjmuje wartości od p-1 do j-1, tak aby każda część zawierała jakąś wartość. Wiersz p odczytuje dane tylko z wiersza p-1, więc wystarczą dwa wiersze.

Algorytm wykonuje do k·n²/2 kroków: około 1.8 × 10^10 dla n = 5000 i k = 2500.

Algorytm

Utwórz prefix, gdzie prefix[j] jest sumą pierwszych j wartości, i ustaw best[j] = prefix[j] dla jednej części.
Dla każdej liczby części p od 2 do k oraz każdego końca j od p do n wyznacz minimum dla i od p-1 do j-1 z max(best[i], prefix[j] - prefix[i]).
Zapisz te minima w nowym wierszu i ustaw go jako best.
Zwróć 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]

Wyszukiwanie binarne największej sumy

Intuicja

Aby przetestować limit c, przejdź od lewej do prawej i dodawaj wartości do bieżącej części, dopóki ich suma nie przekroczy c, a następnie rozpocznij nową część. W ten sposób uzyskasz możliwie najmniej części. W porównaniu z dowolnym poprawnym podziałem pierwsza część utworzona metodą zachłanną kończy się co najmniej tak daleko na prawo, więc następna część zaczyna się w tym podziale w tym samym miejscu lub później. Jej wartości aż do końca tej części tworzą fragment części, który mieści się w limicie, a ponieważ nie ma wartości ujemnych, suma fragmentu nigdy nie przekracza sumy całości. Metoda zachłanna nigdy więc nie pozostaje w tyle.

Mniej niż k części jest równie dobrym wynikiem co k: podzielenie części zawierającej co najmniej dwie wartości na dwie części nigdy nie zwiększa sumy. Test ma więc postać partsNeeded(c) ≤ k.

Wykonaj wyszukiwanie binarne najmniejszego limitu, dla którego test daje wynik pozytywny, między max(nums), ponieważ ta wartość znajduje się w jakiejś części, a sum(nums), która zawsze mieści się w jednej części.

Algorytm

Ustaw lo = max(nums) i hi = sum(nums).
Dopóki lo < hi, oblicz mid = lo + (hi - lo) / 2.
Policz zachłanne części dla mid: zacznij od 1 części o sumie 0; gdy dodanie wartości przekroczyłoby mid, dodaj część i rozpocznij sumowanie od tej wartości.
Jeśli liczba części jest co najwyżej równa k, ustaw hi = mid; w przeciwnym razie ustaw lo = mid + 1.
Zwróć 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

Pułapki i przypadki brzegowe

Rozpoczęcie od lo poniżej max(nums). Algorytm zachłanny umieszcza wartość większą niż limit w osobnej części, więc uznaje limit 5 za wystarczający dla [1, 9] przy k = 2.
Sprawdzanie partsNeeded(c) == k. Dla [3, 0, 4] i k = 3 limit 4 daje części [3, 0], [4], więc żaden limit nie przechodzi testu.
Liczenie części od 0, przez co każdy wynik jest o jeden za mały.
Ustawianie hi = mid - 1, gdy mid działa, co powoduje utratę odpowiedzi, gdy wynosi ona mid.
Rozpoczęcie i w programowaniu dynamicznym od 0. Komórka z mniejszą liczbą wartości niż części zwraca koszt 0, a dla [100, 1, 1] przy k = 3 wynikiem jest 2 zamiast 100.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu Split Array Largest Sum?

O(n log S) czasu i O(1) dodatkowej pamięci, gdzie S jest sumą nums: każde zachłanne sprawdzenie wymaga jednego przejścia, a zakres limitów zmniejsza się o połowę po każdym sprawdzeniu. To około 29 sprawdzeń, gdy S = 5 × 10^8. DP wymaga O(k·n²) czasu.

Dlaczego sprawdzanie wykonalności jest monotoniczne?

Jeśli każda część podziału sumuje się do co najwyżej c, ten sam podział mieści się w limicie c+1. Zatem gdy dany limit działa, każdy większy limit również działa, a odpowiedzi tworzą najpierw serię „nie”, a potem serię „tak”. Wyszukiwanie binarne znajduje pierwszą odpowiedź „tak”.

Czy wyszukiwanie binarne działa z liczbami ujemnymi?

Nie. Wartość ujemna może obniżyć sumę, więc algorytm zachłanny może zamknąć część zbyt wcześnie, a podzielenie części może sprawić, że jeden fragment będzie większy od całości. DP nie zakłada żadnej z tych rzeczy i pozostaje poprawny.

def splitArray(nums, k):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik