Split Array Largest Sum

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

O(n log S) zaman ve O(1) ek alan; burada S , nums dizisinin toplamıdır: her açgözlü kontrol tek bir geçişten oluşur ve sınır değerleri aralığı her kontrolden sonra yarıya iner. S = 5 × 10^8 olduğunda bu yaklaşık 29 kontrol demektir. DP, O(k·n²) zaman alır.

Q: Uygulanabilirlik kontrolü neden monotondur?

Bir bölmenin her parçasının toplamı en fazla c ise, aynı bölme c+1 sınırına da uyar. Dolayısıyla bir sınır işe yarıyorsa, daha büyük her sınır da işe yarar ve yanıtlar önce bir dizi hayır, ardından bir dizi evet şeklindedir. İkili arama ilk eveti bulur.

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

Hayır. Negatif bir değer toplamı düşürebilir; bu nedenle açgözlü yaklaşım bir parçayı çok erken kapatabilir ve bir parçayı bölmek bir parçayı bütünün üzerine çıkarabilir. DP bu varsayımların hiçbirini yapmaz ve doğruluğunu korur.

Zorİkili arama Dinamik programlama

+10

Negatif olmayan tamsayılardan oluşan bir nums dizisi ve bir k tamsayısı alırsın. nums dizisini, her biri boş olmayan, komşu değerlerden oluşan bir dizi parçası olacak ve parçalar sıralarını koruyacak şekilde 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ı kesilecek 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 olur; 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ölmesi 13 tutar. Hiç bölmemek 12 tutar: parçaları soldan sağa 12 sınırının altında paketlemek [6, 2], [9], [4, 7], [3] şeklinde, dört parça verir.

Girdi: nums = [8, 1, 1, 1, 5]k = 2
Çıktı: 8
Açıklama: 8 bir parçanın içinde 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.

Ek soru

Önek toplamlarıyla, açgözlü bir kontrol ikili arama kullanarak her parçanın nerede bittiğini bulabilir. k küçük olduğunda tüm yöntem 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

En iyi bölmeyi doğrudan aramak, dinamik programlama kullanılsa bile O(k·n²) maliyetlidir. Soruyu tersine çevir: k parça, verilen bir sınırın altında kalabilir mi? Tek bir açgözlü geçiş bu soruyu yanıtlar; sınır büyüdükçe yanıt hayırdan evete bir kez döner ve ikili arama bu geçiş noktasını bulur.

Önekler üzerinde dinamik programlama

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

Sezgi

İlk j değeri p parçaya bölmenin en küçük maliyeti için best[p][j] yazın. Son parça nums[i..j-1] ise maliyet, best[p-1][i] ile bu parçanın toplamından büyük olanıdır ve ilk i değerin en iyi bölünmesi sağındaki hiçbir şeye bağlı değildir. Dolayısıyla best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]); her parçada en az bir değer bulunması için i, p-1 ile j-1 arasındadır. p satırı yalnızca p-1 satırını okur, bu yüzden iki satır yeterlidir.

En fazla k·n²/2 adım sürer: n = 5000 ve k = 2500 için yaklaşık 1.8 × 10^10.

Algoritma

prefix[j]'nin ilk j değerin toplamı olduğu prefix'i oluştur ve tek parça için best[j] = prefix[j] olarak ayarla.
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]) ifadesinin minimumunu al.
Bu minimumları yeni bir satırda sakla ve bunu 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

Bir c üst sınırını test etmek için soldan sağa ilerle ve toplamı c sınırını aşmadığı sürece değerleri mevcut parçaya ekle, ardından yeni bir parça başlat. Bu, mümkün olan en az sayıda parçayı kullanır. Geçerli herhangi bir bölmeyle karşılaştırıldığında, açgözlü yöntemin ilk parçası en az onunki kadar sağda biter; dolayısıyla sonraki parçası diğerininkine eşit veya daha ileride başlar. O parçanın sonuna kadar aldığı değerler, sığan bir parçanın bir bölümüdür ve negatif değer olmadığından, bir bölümün toplamı hiçbir zaman bütünün toplamından fazla olmaz. Bu nedenle açgözlü yöntem hiçbir zaman geride kalmaz.

k'den az parça da k parça kadar iyidir: İki veya daha fazla değer içeren bir parçayı ikiye bölmek toplamı asla artırmaz. Dolayısıyla test partsNeeded(c) ≤ k koşuludur.

max(nums) ile, çünkü bu değer bir parçanın içinde yer alır ve her zaman tek bir parçaya sığan sum(nums) arasında, koşulu sağlayan en küçük üst sınırı ikili aramayla bul.

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 altında açgözlü parçaları say: toplamı 0 olan 1 parçayla başla; bir değer eklemek mid değerini aşacaksa bir parça ekle ve toplamı o değerle yeniden başlat.
Sayı en fazla k ise 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

lo değerini max(nums) değerinden küçük başlatmak. Açgözlü yöntem, üst sınırdan büyük bir değeri kendi başına bir parçaya koyar; bu yüzden k = 2 iken [1, 9] için 5 üst sınırının uygun olduğunu bildirir.
partsNeeded(c) == k koşulunu sınamak. [3, 0, 4] ve k = 3 için 4 üst sınırı [3, 0], [4] şeklinde gruplar; dolayısıyla hiçbir üst sınır koşulu sağlayamaz.
Parçaları 0'dan saymak; bu da her sayımı bir eksik yapar.
mid işe yaradığında hi = mid - 1 ayarlamak; bu, yanıt mid olduğunda yanıtı kaybettirir.
DP'deki i değerini 0'dan başlatmak. Parça sayısından daha az değer içeren bir hücre, maliyet olarak 0 okur ve k = 3 iken [100, 1, 1] için 100 yerine 2 bildirir.

Sıkça sorulan sorular3

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

O(n log S) zaman ve O(1) ek alan; burada S, nums dizisinin toplamıdır: her açgözlü kontrol tek bir geçişten oluşur ve sınır değerleri aralığı her kontrolden sonra yarıya iner. S = 5 × 10^8 olduğunda bu yaklaşık 29 kontrol demektir. DP, O(k·n²) zaman alır.

Uygulanabilirlik kontrolü neden monotondur?

Bir bölmenin her parçasının toplamı en fazla c ise, aynı bölme c+1 sınırına da uyar. Dolayısıyla bir sınır işe yarıyorsa, daha büyük her sınır da işe yarar ve yanıtlar önce bir dizi hayır, ardından bir dizi evet şeklindedir. İkili arama ilk eveti bulur.

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

Hayır. Negatif bir değer toplamı düşürebilir; bu nedenle açgözlü yaklaşım bir parçayı çok erken kapatabilir ve bir parçayı bölmek bir parçayı bütünün üzerine çıkarabilir. DP bu varsayımların hiçbirini yapmaz ve doğruluğunu korur.

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

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı