Maximum Product Subarray

+10

Kalikan elemen-elemen dari subarray nums, lalu kembalikan hasil kali terbesar yang dapat dihasilkan oleh subarray mana pun. Subarray terdiri dari elemen-elemen berurutan tanpa celah dan tidak pernah kosong, jadi bahkan array yang berisi nilai negatif pun memiliki jawaban. Nilai nol dan negatif diperbolehkan.

Fungsi

maxProduct(nums: integer-array) → integer

numsinteger-array: bilangan bulat yang akan dikalikan, masing-masing antara -10 dan 10
Mengembalikaninteger: hasil kali terbesar dari subarray yang tidak kosong

Batasan

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
Hasil kali setiap subarray muat dalam bilangan bulat bertanda 32-bit.

Contoh

Input: nums = [2, -5, 3, -2, 0, 4]
Output: 60
Penjelasan: Dua bilangan negatif saling meniadakan: 2 × -5 × 3 × -2 = 60. Angka 0 membagi array menjadi dua, dan angka 4 di sisi lain tidak bisa mengalahkan 60.

Input: nums = [-2, 3, -4, -1]
Output: 24
Penjelasan: Hasil perkalian seluruh array adalah -24 karena array tersebut berisi tiga nilai negatif. Jika elemen terakhir tidak disertakan, tersisa dua nilai negatif: -2 × 3 × -4 = 24, hasil ini lebih besar daripada 12 yang kamu dapatkan jika elemen pertama tidak disertakan.

Input: nums = [-6, 0, -7]
Output: 0
Penjelasan: Subarray yang tidak menyertakan 0 adalah satu bilangan negatif, sedangkan subarray yang menyertakan 0 menghasilkan perkalian 0. Pilihan terbaik adalah subarray [0].

Pertanyaan lanjutan

Bagaimana kamu juga dapat melaporkan posisi awal dan akhir subarray terbaik, tetap dalam waktu O(n) dan ruang O(1)?

Petunjuk

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

0 dari 3 dibuka

Solusi

Mengalikan dengan bilangan negatif membalik urutan hasil perkalian, sehingga hasil perkalian terkecil sejauh ini bisa menjadi yang terbesar satu langkah kemudian, dan nol menghapus semua hasil perkalian. Simpan dua nilai di setiap indeks, bukan satu, yaitu hasil perkalian terbesar dan terkecil dari subarray yang berakhir di sana, dan satu kali penelusuran sudah cukup.

Kalikan setiap subarray dari setiap titik awal

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Tetapkan indeks awal, lalu geser indeks akhir ke kanan sambil mengalikan product dengan setiap elemen baru. Bandingkan hasilnya dengan nilai terbaik setelah setiap langkah agar setiap subarray tercakup tepat satu kali. Mulai best dengan nums[0], karena jawabannya bisa negatif.

Ada sekitar n²/2 pasangan indeks awal dan akhir, dengan satu perkalian untuk setiap pasangan: 2 × 10^8 untuk 20.000 elemen.

Algoritma

Atur best ke nums[0].
Untuk setiap start, atur product ke 1.
Pindahkan end dari start ke indeks terakhir dan kalikan product dengan nums[end].
Jika product lebih besar daripada best, simpan nilainya.
Kembalikan best.

def maxProduct(nums):
    n = len(nums)
    best = nums[0]
    for start in range(n):
        product = 1
        for end in range(start, n):
            # product is now the product of nums[start..end]
            product *= nums[end]
            if product > best:
                best = product
    return best

Pindai dari kedua ujung, mulai ulang dari angka nol

Intuisi

Nilai nol membagi array menjadi rangkaian tanpa nilai nol. Di dalam satu rangkaian, setiap nilai memiliki besar setidaknya 1, jadi subarray yang lebih panjang tidak pernah memiliki hasil kali absolut yang lebih kecil. Yang berubah hanya tandanya. Jika jumlah nilai negatif genap, seluruh rangkaian adalah pilihan terbaik. Jika jumlahnya ganjil, satu nilai negatif harus dihilangkan. Pemotongan terbaik menghilangkan nilai negatif pertama dan semua nilai sebelumnya, atau nilai negatif terakhir dan semua nilai setelahnya. Dengan cara apa pun, kamu mempertahankan akhiran atau awalan rangkaian.

Pemindaian dari kiri dengan hasil kali berjalan memeriksa setiap awalan, lalu mengatur ulang hasilnya ke 1 setelah menemukan 0. Pemindaian dari kanan memeriksa setiap akhiran. Pada [-2, 3, -4, -1], pemindaian dari kiri menghasilkan -2, -6, 24, dan -24, sedangkan pemindaian dari kanan menghasilkan -1, 4, 12, dan -24, jadi jawabannya adalah 24. Argumen ini membutuhkan setiap nilai bukan nol memiliki besar setidaknya 1, yang berlaku untuk bilangan bulat.

Algoritma

Tetapkan best ke nums[0] dan product ke 1.
Telusuri dari kiri ke kanan: kalikan product dengan setiap elemen dan pertahankan nilai yang lebih besar antara best dan product.
Setiap kali product menjadi 0, tetapkan kembali ke 1 agar perulangan berikutnya dimulai dari awal.
Tetapkan kembali product ke 1 dan lakukan penelusuran yang sama dari kanan ke kiri.
Kembalikan best.

def maxProduct(nums):
    best = nums[0]
    # Left to right: the product of every prefix of each zero-free run
    product = 1
    for num in nums:
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1  # a zero ends the run, the next one starts fresh
    # Right to left: the product of every suffix of each zero-free run
    product = 1
    for num in reversed(nums):
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1
    return best

Lacak produk terbesar dan terkecil yang berakhir di sini

Intuisi

Setiap subarray yang berakhir di indeks i hanya berisi nums[i], atau merupakan hasil kali nums[i] dengan subarray yang berakhir di i-1. Saat nums[i] bernilai negatif, hasil kali terbesar berasal dari hasil kali terkecil yang berakhir di i-1. Jadi, simpan keduanya: high dan low, yaitu hasil kali terbesar dan terkecil dari subarray yang berakhir di indeks saat ini. high yang baru adalah nilai terbesar dari num, high × num, dan low × num, sedangkan low yang baru adalah nilai terkecil. Mengambil num saja akan memulai ulang perulangan setelah nilai nol.

Pada contoh pertama, low bernilai -30 saat -2 tiba, dan -30 × -2 = 60 menjadi high, yaitu jawabannya.

Algoritma

Atur high, low dan best ke nums[0].
Untuk setiap elemen berikutnya num, hitung a = high × num dan b = low × num.
Atur high ke nilai terbesar dan low ke nilai terkecil dari num, a dan b.
Atur best ke nilai yang lebih besar antara best dan high.
Kembalikan best.

def maxProduct(nums):
    # high and low: the largest and smallest product of a subarray ending at the current index
    high = low = best = nums[0]
    for num in nums[1:]:
        # Multiply both old values first: a negative num swaps their roles
        a = high * num
        b = low * num
        high = max(num, a, b)
        low = min(num, a, b)
        best = max(best, high)
    return best

Jebakan dan kasus tepi

Hanya melacak hasil kali terbesar. Pada contoh pertama, hasilnya 4, bukan 60, karena nilai -30 yang berubah menjadi 60 saat dikalikan dengan -2 diabaikan.
Menghitung low yang baru dari high yang sudah diperbarui. Simpan high × num dan low × num sebelum mengubah salah satunya.
Memulai best dengan nilai 0 atau 1. [-3] harus menghasilkan -3, karena subarray tidak boleh kosong.
Hanya menjalankan lintasan kiri dari metode dua lintasan. Pada [-2, 3, 4], nilainya tidak pernah lebih dari -2, tetapi sufiks [3, 4] menghasilkan 12.
Di JavaScript, TypeScript, dan Lua, 0 dikalikan bilangan negatif menghasilkan -0, yang dicetak dengan tanda minus. Tambahkan 0 ke hasil sebelum mengembalikannya.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Maximum Product Subarray?

Melacak hasil kali terbesar dan terkecil yang berakhir di setiap indeks membutuhkan waktu O(n) dan ruang O(1). Metode prefiks dan sufiks dua lintasan membutuhkan biaya yang sama. Mengalikan setiap subarray dari setiap titik awal membutuhkan waktu O(n²).

Mengapa kamu memerlukan hasil kali terkecil dalam Maximum Product Subarray?

Bilangan negatif mengubah hasil kali paling negatif yang berakhir pada indeks sebelumnya menjadi hasil kali terbesar. Simpan hanya hasil kali terbesar, sehingga kandidat tersebut tidak tersedia saat kamu membutuhkannya. Dalam [3, -2, -4], hasil kali terkecil sebelum -4 adalah -6, dan -6 × -4 = 24 adalah jawabannya.

Apa perbedaan Maximum Product Subarray dengan Maximum Subarray?

Untuk penjumlahan, total berjalan negatif hanya akan merugikan, jadi satu nilai untuk setiap indeks sudah cukup. Untuk perkalian, nilai berjalan yang negatif bisa menjadi yang terbaik setelah dikalikan dengan bilangan negatif lain, dan nol akan mengatur ulang semuanya. Jadi, versi perkalian menyimpan hasil perkalian terbesar dan terkecil pada setiap indeks.

def maxProduct(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [2, -5, 3, -2, 0, 4]

Output yang diharapkan

Maximum Product Subarray

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Kalikan setiap subarray dari setiap titik awal

Pindai dari kedua ujung, mulai ulang dari angka nol

Lacak produk terbesar dan terkecil yang berakhir di sini

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa