Split Array Largest Sum

Q: Berapa kompleksitas waktu dari Split Array Largest Sum?

Waktu O(n log S) dan ruang tambahan O(1) , dengan S sebagai jumlah nums : setiap pemeriksaan greedy hanya melakukan satu kali lintasan, dan rentang batas berkurang setengah setelah setiap pemeriksaan. Jumlahnya sekitar 29 pemeriksaan saat S = 5 × 10^8 . DP membutuhkan waktu O(k·n²) .

Q: Mengapa pemeriksaan kelayakan bersifat monoton?

Jika setiap bagian dari pembagian jumlahnya paling banyak c , pembagian yang sama juga muat di bawah c+1 . Jadi, setelah batas tertentu berhasil, semua batas yang lebih besar juga berhasil, dan jawaban membentuk rangkaian tidak diikuti rangkaian ya. Pencarian biner menemukan jawaban ya yang pertama.

Q: Apakah binary search berfungsi dengan angka negatif?

Tidak. Nilai negatif dapat mengurangi jumlah, sehingga algoritma greedy mungkin menutup bagian terlalu cepat, dan membagi suatu bagian dapat membuat satu potongan lebih besar daripada keseluruhannya. DP tidak membuat asumsi tersebut dan tetap benar.

SulitBinary search Dynamic programming

+10

Kamu mendapatkan sebuah array nums berisi bilangan bulat nonnegatif dan sebuah bilangan bulat k. Bagi nums menjadi tepat k bagian, dengan setiap bagian berupa rangkaian nilai bersebelahan yang tidak kosong dan urutan bagian tetap dipertahankan. Setiap bagian memiliki jumlah, dan biaya pembagian adalah jumlah terbesar dari bagian-bagian tersebut.

Kembalikan biaya terkecil yang dapat dicapai dengan membagi menjadi k bagian.

Fungsi

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

numsinteger-array: nilai-nilai nonnegatif, secara berurutan
kinteger: jumlah bagian berurutan untuk membaginya
Mengembalikaninteger: nilai terkecil yang mungkin dari jumlah bagian terbesar

Batasan

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length
Setiap bagian memiliki setidaknya satu nilai. Bagian yang semua nilainya 0 berjumlah 0, dan itu diperbolehkan.

Contoh

Input: nums = [6, 2, 9, 4, 7, 3]k = 3
Output: 13
Penjelasan: Pembagian [6, 2], [9, 4], [7, 3] membutuhkan biaya 13. Tidak ada pembagian yang membutuhkan biaya 12: mengemas bagian-bagian dari kiri ke kanan dengan batas 12 menghasilkan [6, 2], [9], [4, 7], [3], sebanyak empat bagian.

Input: nums = [8, 1, 1, 1, 5]k = 2
Output: 8
Penjelasan: Angka 8 berada di salah satu bagian, jadi tidak ada pemisahan yang biayanya kurang dari 8. [8] dan [1, 1, 1, 5] sama-sama berjumlah 8.

Pertanyaan lanjutan

Dengan jumlah prefiks, pemeriksaan greedy dapat menemukan akhir setiap bagian menggunakan pencarian biner. Seberapa cepat keseluruhan metode ini jika k kecil?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Mencari pembagian terbaik secara langsung membutuhkan biaya O(k·n²), bahkan dengan pemrograman dinamis. Balik pertanyaannya: bisakah k bagian tetap berada di bawah batas tertentu? Satu lintasan greedy menjawabnya, jawabannya berubah dari tidak menjadi ya satu kali saat batas bertambah, dan pencarian biner menemukan perubahan itu.

Pemrograman dinamis pada prefix

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Tulis best[p][j] untuk biaya terkecil dalam membagi j nilai pertama menjadi p bagian. Jika bagian terakhir adalah nums[i..j-1], biayanya adalah nilai yang lebih besar antara best[p-1][i] dan jumlah bagian tersebut, dan pembagian terbaik untuk i nilai pertama tidak bergantung pada apa pun di sebelah kanannya. Jadi, best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), dengan i dari p-1 hingga j-1 agar setiap bagian berisi sebuah nilai. Baris p hanya membaca baris p-1, jadi dua baris sudah cukup.

Algoritma ini berjalan hingga k·n²/2 langkah: sekitar 1.8 × 10^10 untuk n = 5000 dan k = 2500.

Algoritma

Buat prefix, dengan prefix[j] sebagai jumlah dari j nilai pertama, lalu tetapkan best[j] = prefix[j] untuk satu bagian.
Untuk setiap jumlah bagian p dari 2 hingga k, dan setiap nilai akhir j dari p hingga n, ambil nilai minimum dari i mulai p-1 hingga j-1 untuk max(best[i], prefix[j] - prefix[i]).
Simpan nilai minimum tersebut di baris baru dan jadikan best.
Kembalikan 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]

Pencarian biner untuk jumlah terbesar

Intuisi

Untuk menguji batas c, telusuri dari kiri ke kanan dan tambahkan nilai ke bagian saat ini selama jumlahnya tidak melebihi c, lalu mulai bagian baru. Cara ini menggunakan jumlah bagian sesedikit mungkin. Dibandingkan dengan pemisahan valid mana pun, bagian pertama greedy berakhir setidaknya sama jauh ke kanan, jadi bagian berikutnya dimulai pada atau setelah bagian berikutnya dalam pemisahan lain. Nilai-nilainya hingga akhir bagian itu merupakan potongan dari suatu bagian yang memenuhi batas, dan karena tidak ada nilai negatif, jumlah suatu potongan tidak pernah melebihi jumlah keseluruhannya. Jadi, greedy tidak pernah tertinggal.

Jumlah bagian kurang dari k sama baiknya dengan k: membagi bagian yang terdiri dari dua nilai atau lebih menjadi dua bagian tidak pernah menaikkan jumlahnya. Jadi, pengujiannya adalah partsNeeded(c) ≤ k.

Lakukan pencarian biner untuk batas terkecil yang memenuhi syarat, di antara max(nums), karena nilai itu berada di suatu bagian, dan sum(nums), yang selalu muat dalam satu bagian.

Algoritma

Tetapkan lo = max(nums) dan hi = sum(nums).
Selama lo < hi, ambil mid = lo + (hi - lo) / 2.
Hitung bagian greedy di bawah mid: mulai dengan 1 bagian dan jumlah 0; saat menambahkan sebuah nilai akan membuat jumlahnya melewati mid, tambahkan satu bagian dan mulai lagi jumlahnya dari nilai tersebut.
Jika jumlah bagian paling banyak k, tetapkan hi = mid; jika tidak, tetapkan lo = mid + 1.
Kembalikan 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

Jebakan dan kasus tepi

Memulai lo di bawah max(nums). Pendekatan greedy menempatkan nilai yang lebih besar dari batas dalam bagiannya sendiri, sehingga melaporkan batas 5 sebagai nilai yang memenuhi syarat untuk [1, 9] dengan k = 2.
Menguji partsNeeded(c) == k. Untuk [3, 0, 4] dan k = 3, batas 4 mengemas [3, 0], [4], sehingga tidak ada batas yang memenuhi syarat.
Menghitung bagian mulai dari 0, sehingga setiap hitungan lebih kecil satu.
Mengatur hi = mid - 1 saat mid berhasil, sehingga jawaban hilang jika nilainya adalah mid.
Memulai i dalam DP dari 0. Sel yang memiliki lebih sedikit nilai daripada jumlah bagian akan dibaca sebagai biaya 0, dan [100, 1, 1] dengan k = 3 menghasilkan 2, bukan 100.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Split Array Largest Sum?

Waktu O(n log S) dan ruang tambahan O(1), dengan S sebagai jumlah nums: setiap pemeriksaan greedy hanya melakukan satu kali lintasan, dan rentang batas berkurang setengah setelah setiap pemeriksaan. Jumlahnya sekitar 29 pemeriksaan saat S = 5 × 10^8. DP membutuhkan waktu O(k·n²).

Mengapa pemeriksaan kelayakan bersifat monoton?

Jika setiap bagian dari pembagian jumlahnya paling banyak c, pembagian yang sama juga muat di bawah c+1. Jadi, setelah batas tertentu berhasil, semua batas yang lebih besar juga berhasil, dan jawaban membentuk rangkaian tidak diikuti rangkaian ya. Pencarian biner menemukan jawaban ya yang pertama.

Apakah binary search berfungsi dengan angka negatif?

Tidak. Nilai negatif dapat mengurangi jumlah, sehingga algoritma greedy mungkin menutup bagian terlalu cepat, dan membagi suatu bagian dapat membuat satu potongan lebih besar daripada keseluruhannya. DP tidak membuat asumsi tersebut dan tetap benar.

def splitArray(nums, k):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan