Split Array Largest Sum

Przyjrzyj się ostatniej części podziału. Jeśli pierwsze j wartości tworzą p części, ostatnia część to pewien ciąg nums[i..j-1], a pierwsze i wartości tworzą pozostałe p-1 części. Koszt jest większą z dwóch liczb: kosztu tych p-1 części oraz sumy ostatniego ciągu. Niezależnie od tego, jaki jest ostatni ciąg, chcesz podzielić pierwsze i wartości możliwie najniższym kosztem, a ten najlepszy podział nie zależy od niczego, co znajduje się po jego prawej stronie. Możesz więc obliczyć go raz i wykorzystać ponownie.

Oznaczmy przez best[p][j] najmniejszy koszt podziału pierwszych j wartości na p części. Przy jednej części nie ma wyboru: best[1][j] to suma pierwszych j wartości. Dla większej liczby części wypróbuj każdy początek i ostatniej części: best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), gdzie prefix[j] jest sumą pierwszych j wartości. Początek i mieści się w zakresie od p-1, ponieważ p-1 niepustych części wymaga co najmniej p-1 wartości, do j-1, ponieważ ostatnia część musi zawierać jedną wartość. Odpowiedzią jest best[k][n]. Wiersz p odczytuje tylko wiersz p-1, więc wystarczą dwa wiersze długości n+1.

W pierwszym przykładzie podział [6, 2, 9, 4] na dwie części może zakończyć pierwszą część po 6 (koszt max(6, 15) = 15), po 2 (max(8, 13) = 13) lub po 9 (max(17, 4) = 17), więc best[2][4] = 13. Następnie best[3][6] sprawdza ostatnią część [7, 3] i otrzymuje max(13, 10) = 13, czego nie da się poprawić żadnym innym początkiem.

Problemem jest czas działania. Jest k wierszy, n końców w każdym wierszu i maksymalnie n początków dla każdego końca: maksymalnie k·n²/2 kroków. Przy n = 5000 i k = 2500 wewnętrzna pętla wykonuje około 1.8 × 10^10 razy: 18 sekund nawet przy 10^9 prostych kroków na sekundę. Warto jednak znać programowanie dynamiczne: nigdy nie zakłada, że wartości są nieujemne, więc działa także tam, gdzie szybka metoda zawodzi.

Odwróćmy pytanie. Wybierz limit c i zapytaj: czy da się podzielić nums na k części, tak aby suma każdej z nich była nie większa niż c? Odpowiedzią na zadanie jest najmniejszy limit, dla którego odpowiedź brzmi „tak”. To pytanie jest znacznie łatwiejsze od pierwotnego z dwóch powodów.

Po pierwsze, odpowiada na nie jedno zachłanne przejście. Idź od lewej do prawej i dodawaj wartości do bieżącej części, dopóki jej suma nie przekracza c; gdy następna wartość spowodowałaby przekroczenie c, zamknij część i zacznij nową od tej wartości. W ten sposób uzyskasz najmniejszą liczbę części, jakiej może użyć dowolny podział przy tym limicie. Porównaj ten podział z dowolnym innym poprawnym podziałem, część po części. Obie pierwsze części zaczynają się od pierwszej wartości, a algorytm zachłanny zatrzymuje się dopiero wtedy, gdy kolejna wartość się nie mieści, więc jego pierwsza część kończy się co najmniej tak daleko. Druga część algorytmu zachłannego zaczyna się wtedy w miejscu nie wcześniejszym niż początek drugiej części drugiego podziału. Wartości do końca tamtej części stanowią jej fragment, a ponieważ nie ma wartości ujemnych, suma fragmentu nigdy nie przekracza sumy całości, więc się mieszczą i algorytm zachłanny ponownie sięga co najmniej tak daleko. Algorytm zachłanny nigdy nie zostaje w tyle, więc nigdy nie potrzebuje więcej części.

Po drugie, mniejsza liczba części niż k jest równie dobra jak dokładnie k części. Jeśli algorytm zachłanny potrzebuje m < k części, podziel część zawierającą co najmniej dwie wartości na dwie części. Ich sumy nie przekraczają sumy całości, ponieważ żadna wartość nie jest ujemna, a ponieważ n ≥ k, zawsze można znaleźć taką część, dopóki nie uzyskasz k części. Zatem warunek testu to partsNeeded(c) ≤ k.

Teraz kluczowa właściwość: test jest monotoniczny. Jeśli limit c działa, to c+1 też działa, ponieważ ten sam podział nadal mieści się w większym limicie. Dla limitów od max(nums) do sum(nums) odpowiedzi układają się w ciąg: nie, nie, ..., nie, tak, tak, ..., tak, a szukasz pierwszego „tak”. Zakres jest bezpieczny na obu końcach: żaden limit mniejszy niż max(nums) nie pomieści tej wartości, a suma wszystkich wartości zawsze mieści się w jednej części. Pierwsze „tak” odpowiada też rzeczywistemu kosztowi, a nie tylko granicy: gdyby suma żadnej części w tym podziale nie była równa c, limit c-1 również by wystarczył.

Prześledź pierwszy przykład: [6, 2, 9, 4, 7, 3] dla k = 3. Limity mieszczą się w zakresie od 9 do 31. Przy limicie 20 otrzymujemy części [6, 2, 9], [4, 7, 3]: 2 części, tak, więc zakres zmienia się na 9–20. Przy limicie 14 otrzymujemy [6, 2], [9, 4], [7, 3]: 3 części, tak, zakres 9–14. Przy limicie 11 otrzymujemy [6, 2], [9], [4, 7], [3]: 4 części, nie, zakres 12–14. Przy limicie 13 potrzeba 3 części, tak, zakres 12–13. Przy limicie 12 potrzeba 4 części, nie, więc odpowiedzią jest 13.

Każde przejście odczytuje n wartości, a zakres za każdym razem zmniejsza się o połowę. Przy sumie S wynoszącej maksymalnie 5 × 10^8 daje to około 29 przejść po 5000 wartości, czyli mniej więcej 150000 kroków.