Split Array Largest Sum

Q: Split Array Largest Sum işleminin zaman karmaşıklığı nedir?

İkili arama, O(n log S) zamanda çalışır; burada n , nums uzunluğu ve S ise toplamıdır. Her açgözlü kontrol, dizi üzerinde tek bir geçiştir ve üst sınırlar aralığı her kontrolden sonra yarıya iner: S = 5 × 10^8 olduğunda yaklaşık 29 kontrol gerekir. O(1) ek alan kullanır. DP, O(k·n²) zamanda ve O(n) alanda çalışır.

Q: Uygulanabilirlik kontrolü neden monotoniktir?

Bir bölmenin her parçasının toplamı en fazla c ise aynı bölmenin her parçası da en fazla c+1 olur. Dolayısıyla bir üst sınır işe yararsa daha büyük tüm üst sınırlar da işe yarar; bir üst sınır başarısız olursa daha küçük tüm üst sınırlar da başarısız olur. Yanıtlar, önce bir hayır dizisi ardından bir evet dizisi oluşturur; ikili aramanın sınırı bulmak için ihtiyaç duyduğu şey tam olarak budur.

Q: Açgözlü kontrol neden en az sayıda parçayı bulur?

Greedy, bir sonraki değer üst sınırı aşacak olana kadar bir bölüme değerler eklemeye devam eder. Bunu, geçerli herhangi bir bölmeyle parça parça karşılaştırın. Her greedy bölümü, aynı numaralı diğer bölmenin bölümünün başladığı yerde veya daha sonra başlar; dolayısıyla o bölümün sonuna kadar olan değerleri, üst sınırın altında kalan bir bölümün parçasıdır. Hiçbir değer negatif olmadığından bu parça da üst sınırın altında kalır ve greedy en az o kadar ilerler. Greedy hiçbir zaman geride kalmadığından diziyi, herhangi bir bölme kadar az parçayla kapsar.

Q: İkili arama negatif sayılarla çalışır mı?

Hayır. Negatif değerlerde, bir değer eklemek toplamı düşürebilir; bu nedenle açgözlü yaklaşım bir parçayı çok erken kapatabilir ve işe yarayan bir bölmeyi kaçırabilir. Bir parçayı bölmek, parçalardan birinin toplamını bütün parçanın toplamından da büyük hâle getirebilir; bu yüzden k parçadan daha az parçaya sahip olmak artık k parçanın işe yarayacağı anlamına gelmez. DP bu varsayımların hiçbirini yapmaz ve O(k·n²) zaman karmaşıklığında doğru kalır.

Zorİkili arama Dinamik programlama

+10

Sana negatif olmayan tam sayılardan oluşan bir nums dizisi ve bir k tam sayısı veriliyor. nums dizisini, her biri boş olmayan ve yan yana gelen değerlerden oluşan, sıralarını koruyan tam olarak k parçaya böl. Her parçanın bir toplamı vardır ve bölmenin maliyeti bu toplamların en büyüğüdür.

k parçaya yapılan herhangi bir bölmenin ulaşabileceği en küçük maliyeti döndür.

Fonksiyon

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

numsinteger-array: negatif olmayan değerler, sırasıyla
kinteger: onları kesmek için bitişik parça sayısı
Döndürürinteger: en büyük parça toplamının mümkün olan en küçük değeri

Kısıtlar

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length
Her parça en az bir değer içerir. Değerlerinin tümü 0 olan bir parçanın toplamı 0'dır; buna izin verilir.

Örnekler

Girdi: nums = [6, 2, 9, 4, 7, 3]k = 3
Çıktı: 13
Açıklama: [6, 2], [9, 4], [7, 3] bölmesinin toplamları 8, 13 ve 10 olduğundan maliyeti 13'tür. Maliyeti 12 olan bir bölme yoktur: parçaları soldan sağa, her toplam en fazla 12 olacak şekilde yerleştirince [6, 2], [9], [4, 7], [3] elde edilir; oysa yalnızca üç parçaya izin verilir.

Girdi: nums = [8, 1, 1, 1, 5]k = 2
Çıktı: 8
Açıklama: 8 bir bölümde yer alır, bu nedenle hiçbir bölme 8'den daha düşük maliyetli olamaz. [8] ve [1, 1, 1, 5] toplamda 8 eder; dolayısıyla 8'e ulaşılır.

Gönderirken +20 gizli test

Ek soru

Her açgözlü kontrol, tüm n değerlerini okur. Önek toplamlarıyla bir kontrol, bunun yerine ikili arama kullanarak her parçanın nerede bittiğini bulabilir. k küçük ve nums uzun olduğunda yöntemin tamamı ne kadar hızlı olur?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Bu iki gereksinim birbiriyle çelişiyor: tam olarak k parça kullanmalı ve en büyük parçayı olabildiğince küçük tutmalısın. k-1 kesimin her olası yerini denemek aramayı patlatır; önekler üzerinde dinamik programlama kullanmak bunu O(k·n²) düzeyine indirir, ancak 5000 değer için hâlâ çok yavaştır. Hızlı yöntem soruyu tersine çevirir. En iyi bölmeyi aramak yerine, bir üst sınır tahmin edip k parçanın bu sınırı aşmadan kalıp kalamayacağını sorarsın. Tek bir açgözlü geçiş bunu yanıtlar; üst sınır arttıkça yanıt yalnızca bir kez değişir ve ikili arama bu değişimi yaklaşık 29 geçişte bulur.

Önekler üzerinde dinamik programlama

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Bir parçalamanın son kısmına bak. İlk j değer p parça oluşturuyorsa, son parça nums[i..j-1] biçiminde bir dizi olur ve ilk i değer diğer p-1 parçayı oluşturur. Maliyet iki sayıdan büyük olanıdır: bu p-1 parçanın maliyeti ve son dizinin toplamı. Son dizi ne olursa olsun, ilk i değeri olabildiğince düşük maliyetle parçalamak istersin ve bu en iyi parçalama sağındaki hiçbir şeye bağlı değildir. Böylece bunu bir kez hesaplayıp yeniden kullanabilirsin.

İlk j değeri p parçaya ayırmanın en düşük maliyeti için best[p][j] yazalım. Tek parça için seçenek yoktur: best[1][j], ilk j değerin toplamıdır. Daha fazla parça için son parçanın her başlangıç değeri i denenir: best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]); burada prefix[j], ilk j değerin toplamıdır. p-1 boş olmayan parça için en az p-1 değer gerektiğinden, başlangıç değeri i p-1’den başlar; son parçada bir değer bulunması gerektiğinden j-1’e kadar gider. Yanıt best[k][n] olur. p satırı yalnızca p-1 satırını okur; bu nedenle uzunluğu n+1 olan iki satır yeterlidir.

İlk örnekte, [6, 2, 9, 4] dizisini iki parçaya ayırırken ilk parçayı 6’dan sonra bitirmenin maliyeti max(6, 15) = 15, 2’den sonra bitirmenin maliyeti max(8, 13) = 13, 9’dan sonra bitirmenin maliyeti ise max(17, 4) = 17 olur; dolayısıyla best[2][4] = 13. Ardından best[3][6], son parça olarak [7, 3] dizisini dener ve max(13, 10) = 13 sonucunu bulur; başka hiçbir başlangıç daha iyi sonuç vermez.

Asıl sorun işlem miktarıdır. k satır, her satırda n bitiş noktası ve her bitiş noktası için en fazla n başlangıç vardır: en fazla k·n²/2 adım. n = 5000 ve k = 2500 için iç döngü yaklaşık 1.8 × 10^10 kez çalışır: saniyede 10^9 basit adımda bile 18 saniye. Yine de bu DP’yi bilmekte fayda var: değerlerin negatif olmadığını varsaymaz; bu yüzden hızlı yöntemin işe yaramadığı durumlarda da çalışmaya devam eder.

Algoritma

prefix'i oluştur; burada prefix[j], ilk j değerin toplamıdır.
Tek parça için satırı ayarla: best[j] = prefix[j].
2'den k'ye kadar her parça sayısı p ve p'den n'ye kadar her bitiş noktası j için, p-1'den j-1'e kadar i değerleri arasındaki max(best[i], prefix[j] - prefix[i]) değerlerinin minimumunu al.
Bu minimumları yeni bir satırda sakla ve bu satırı best yap.
best[n] değerini döndür.

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]

En büyük toplam üzerinde ikili arama

Sezgi

Soruyu tersine çevir. Bir üst sınır c seç ve şunu sor: nums, her parçanın toplamı en fazla c olacak şekilde k parçaya bölünebilir mi? Problemin yanıtı, bu soruya evet yanıtı veren en küçük üst sınırdır. Bu soru, iki nedenle asıl problemden çok daha kolaydır.

İlk olarak, tek bir açgözlü geçiş soruyu yanıtlar. Soldan sağa ilerle ve toplamı c sınırını aşmadığı sürece değerleri geçerli parçaya eklemeye devam et; sıradaki değer toplamı c'nin üzerine çıkaracaksa parçayı bitir ve bu değerle yeni bir parça başlat. Bu yöntem, üst sınırın altında herhangi bir bölmenin kullanabileceği en az sayıda parçayı kullanır. Bunu diğer geçerli bölmelerle parça parça karşılaştır. Her iki ilk parça da ilk değerden başlar ve açgözlü yöntem yalnızca sıradaki değer sığmadığında durur; bu nedenle açgözlü yöntemin ilk parçası en az diğerininki kadar sağda biter. Açgözlü yöntemin ikinci parçası da diğer ikinci parçanın başladığı yerden ya da daha ileriden başlar. Bu parçanın bitişine kadarki değerleri, diğer parçanın bir bölümüdür ve negatif değer olmadığında bir bölümün toplamı hiçbir zaman bütün parçanın toplamından fazla olmaz; dolayısıyla bu değerler sığar ve açgözlü yöntem yine en az diğer yöntem kadar ilerler. Açgözlü yöntem hiçbir zaman geride kalmaz, dolayısıyla daha fazla parçaya ihtiyaç duymaz.

İkinci olarak, k'den daha az parça kullanmak, tam olarak k parça kullanmak kadar iyidir. Açgözlü yöntem m < k parçaya ihtiyaç duyuyorsa, iki veya daha fazla değer içeren bir parçayı ikiye böl. Negatif değer olmadığından, bu iki parçanın toplamı bütün parçanın toplamından fazla olamaz ve n ≥ k olduğundan k'ye ulaşana kadar böyle bir parça her zaman bulunur. Bu yüzden test partsNeeded(c) ≤ k şeklindedir.

Şimdi kilit özellik: test monotoniktir. Üst sınır c işe yarıyorsa c+1 de işe yarar; çünkü aynı bölme daha büyük bir üst sınıra da sığar. max(nums) ile sum(nums) arasındaki üst sınırlar için yanıtlar hayır, hayır, ..., hayır, evet, evet, ..., evet şeklindedir ve sen ilk eveti ararsın. Aralığın her iki ucu da güvenlidir: max(nums)'den küçük hiçbir üst sınır o değeri alamaz ve toplam her zaman tek bir parçaya sığar. İlk evet aynı zamanda gerçek bir maliyettir, yalnızca bir sınır değildir: bu bölmedeki hiçbir parçanın toplamı tam olarak c değilse c-1 üst sınırı da işe yarardı.

[6, 2, 9, 4, 7, 3] ve k = 3 olan ilk örneği adım adım izleyelim. Üst sınırlar 9'dan 31'e kadar gider. 20 üst sınırı [6, 2, 9], [4, 7, 3] şeklinde gruplar: 2 parça, evet; böylece aralık 9 ile 20 olur. 14 üst sınırı [6, 2], [9, 4], [7, 3] şeklinde gruplar: 3 parça, evet; aralık 9 ile 14 olur. 11 üst sınırı [6, 2], [9], [4, 7], [3] şeklinde gruplar: 4 parça, hayır; aralık 12 ile 14 olur. 13 üst sınırı 3 parça gerektirir, evet; aralık 12 ile 13 olur. 12 üst sınırı 4 parça gerektirir, hayır; dolayısıyla yanıt 13'tür.

Her geçiş n değeri okur ve aralık her seferinde yarıya iner. En fazla 5 × 10^8 olan toplam S için bu, 5000 değer üzerinde yaklaşık 29 geçiş, yani kabaca 150000 adım demektir.

Algoritma

lo = max(nums) ve hi = sum(nums) olarak ayarla.
lo < hi olduğu sürece mid = lo + (hi - lo) / 2 değerini al.
mid üst sınırı altında greedy'nin ihtiyaç duyduğu parça sayısını say: 1 parçayla ve toplamı 0 olarak başla; bir değer eklendiğinde toplam mid değerini aşacaksa, bir parça ekle ve toplamı o değerden başlat.
Sayı k değerinden küçük veya eşitse hi = mid olarak ayarla; aksi hâlde lo = mid + 1 olarak ayarla.
lo değerini döndür.

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

Tuzaklar ve uç durumlar

Arama kısa, bu yüzden hatalar açgözlü kontrolde ve sınırlarda yatıyor.

lo değerini max(nums) değerinden küçük başlatmak. Açgözlü kontrol, üst sınırdan büyük bir değeri kendi başına bir parçaya koyup devam eder; bu yüzden k = 2 için [1, 9] dizisinde 5 üst sınırını uygun olarak bildirir. En büyük değerden başlatın ya da tek bir değer üst sınırı aştığında kontrolün başarısız olmasını sağlayın.
partsNeeded(c) == k koşulunu test etmek. Açgözlü yöntem çoğu zaman k değerinden daha az parçaya ihtiyaç duyar: k = 3 için [3, 0, 4] dizisinde 4 üst sınırı, [3, 0], [4] parçalarına sığdırır. == ile hiçbir üst sınır koşulu geçemez. Daha az parça her zaman daha fazla parçaya bölünebilir; bu nedenle ≤ k koşulunu test edin.
Parça sayımına 0'dan başlamak. İlk parça, herhangi bir değer kapasitesini aşmadan önce zaten vardır; bu nedenle sayım 1'den başlar.
mid işe yaradığında hi = mid - 1 yapmak. Bu, yanıtın kendisini atlayabilir. hi = mid değerini koruyun ve lo < hi koşuluyla döngü kurun.
DP'de i değerini 0'dan başlatmak. i < p-1 olan best[i] hücresi, parça sayısından daha az değer anlamına gelir; hiçbir bölme bunu sağlayamaz ve sıfırlarla doldurulmuş bir satırda maliyet 0 olarak okunur. [100, 1, 1] için k = 3 olduğunda DP, 100 yerine 2 bildirir. i değerini p-1 konumundan başlatın.
Daha büyük sınırlarda taşma. Burada toplam en fazla 5 × 10^8 olduğundan, 32 bit tam sayılar bunu tutabilir. Değerler 10^6 değerine ulaşırsa, 2148 tanesi bile 2^31-1 değerini aşar; bu nedenle toplamlar için 64 bit kullanın.

Sıkça sorulan sorular4

Split Array Largest Sum işleminin zaman karmaşıklığı nedir?

İkili arama, O(n log S) zamanda çalışır; burada n, nums uzunluğu ve S ise toplamıdır. Her açgözlü kontrol, dizi üzerinde tek bir geçiştir ve üst sınırlar aralığı her kontrolden sonra yarıya iner: S = 5 × 10^8 olduğunda yaklaşık 29 kontrol gerekir. O(1) ek alan kullanır. DP, O(k·n²) zamanda ve O(n) alanda çalışır.

Uygulanabilirlik kontrolü neden monotoniktir?

Bir bölmenin her parçasının toplamı en fazla c ise aynı bölmenin her parçası da en fazla c+1 olur. Dolayısıyla bir üst sınır işe yararsa daha büyük tüm üst sınırlar da işe yarar; bir üst sınır başarısız olursa daha küçük tüm üst sınırlar da başarısız olur. Yanıtlar, önce bir hayır dizisi ardından bir evet dizisi oluşturur; ikili aramanın sınırı bulmak için ihtiyaç duyduğu şey tam olarak budur.

Açgözlü kontrol neden en az sayıda parçayı bulur?

Greedy, bir sonraki değer üst sınırı aşacak olana kadar bir bölüme değerler eklemeye devam eder. Bunu, geçerli herhangi bir bölmeyle parça parça karşılaştırın. Her greedy bölümü, aynı numaralı diğer bölmenin bölümünün başladığı yerde veya daha sonra başlar; dolayısıyla o bölümün sonuna kadar olan değerleri, üst sınırın altında kalan bir bölümün parçasıdır. Hiçbir değer negatif olmadığından bu parça da üst sınırın altında kalır ve greedy en az o kadar ilerler. Greedy hiçbir zaman geride kalmadığından diziyi, herhangi bir bölme kadar az parçayla kapsar.

İkili arama negatif sayılarla çalışır mı?

Hayır. Negatif değerlerde, bir değer eklemek toplamı düşürebilir; bu nedenle açgözlü yaklaşım bir parçayı çok erken kapatabilir ve işe yarayan bir bölmeyi kaçırabilir. Bir parçayı bölmek, parçalardan birinin toplamını bütün parçanın toplamından da büyük hâle getirebilir; bu yüzden k parçadan daha az parçaya sahip olmak artık k parçanın işe yarayacağı anlamına gelmez. DP bu varsayımların hiçbirini yapmaz ve O(k·n²) zaman karmaşıklığında doğru kalır.

Python

def splitArray(nums, k):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

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

Beklenen