Persediaan Temu Duga Pengaturcaraan · Pelajaran

Subtatasusunan Maksimum dan Subtatasusunan Hasil Darab Maksimum

Gunakan algoritma Kadane pada maximum-sum-subarray dan lanjutkannya untuk menjejaki nilai maksimum serta minimum bagi variasi hasil darab.

Pelajaran 2 daripada 413 langkah

Subtatasusunan Maksimum dan Subtatasusunan Hasil Darab Maksimum ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.

Masalah Subtatasusunan Jumlah Maksimum

Masalah Subtatasusunan Jumlah Maksimum meminta anda mencari subtatasusunan berturutan dalam tatasusunan satu dimensi nombor yang mempunyai jumlah terbesar. Sebagai contoh, dalam [-2, 1, -3, 4, -1, 2, 1, -5, 4], subtatasusunan [4, -1, 2, 1] memberikan jumlah maksimum 6. Pendekatan cuba semua kemungkinan O(n²) menyemak semua subtatasusunan, tetapi algoritma Kadane menyelesaikannya dalam O(n).

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Brute force: O(n^2)
max_sum = float('-inf')
for i in range(len(nums)):
    curr = 0
    for j in range(i, len(nums)):
        curr += nums[j]
        max_sum = max(max_sum, curr)
print(max_sum)  # 6

Intuisi Algoritma Kadane

Algoritma Kadane membuat satu laluan melalui tatasusunan sambil mengekalkan current_sum terkumpul. Pada setiap elemen, anda menentukan: adakah lebih baik untuk memanjangkan subtatasusunan sedia ada atau memulakan semula daripada elemen ini? Jika current_sum menjadi negatif, nilai itu hanya akan menjejaskan mana-mana subtatasusunan pada masa hadapan, jadi mulakan semula. Hubungan rekursinya ialah current_sum = max(num, current_sum + num).

def max_subarray(nums):
    max_sum = current_sum = nums[0]
    for num in nums[1:]:
        # Extend or start fresh?
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(nums))  # 6

Menjejak Algoritma Kadane

Mari kita jejak algoritma Kadane pada [-2, 1, -3, 4, -1, 2, 1, -5, 4]: mulakan dengan curr=-2, max=-2. Pada 1: curr=max(1,-2+1)=1, max=1. Pada -3: curr=max(-3,1-3)=-2, max=1. Pada 4: curr=max(4,-2+4)=4, max=4. Pada -1: curr=3, max=4. Pada 2: curr=5, max=5. Pada 1: curr=6, max=6. Pada -5: curr=1. Pada 4: curr=5, max=6. Algoritma ini mengenal pasti dengan betul subtatasusunan yang berakhir pada indeks 6 sebagai pilihan optimum.

def max_subarray_trace(nums):
    curr = max_sum = nums[0]
    for i, num in enumerate(nums[1:], 1):
        new_curr = max(num, curr + num)
        max_sum = max(max_sum, new_curr)
        print(f'i={i}, num={num}, curr: {curr}->{new_curr}, max={max_sum}')
        curr = new_curr
    return max_sum

max_subarray_trace([-2, 1, -3, 4, -1, 2, 1, -5, 4])

Memulangkan Subtatasusunan Sebenar

Jika penemuduga meminta anda memulangkan subtatasusunan itu sendiri (bukan sekadar jumlahnya), anda perlu menjejak indeks mula dan tamat. Apabila anda memulakan semula (kerana num > current_sum + num), kemas kini temp_start. Apabila anda mengemas kini max_sum, simpan temp_start sebagai start dan indeks semasa sebagai end. Ini menambah beban O(1) kepada algoritma O(n) yang sama.

def max_subarray_indices(nums):
    max_sum = curr = nums[0]
    start = end = temp_start = 0
    for i in range(1, len(nums)):
        if nums[i] > curr + nums[i]:
            curr = nums[i]
            temp_start = i
        else:
            curr += nums[i]
        if curr > max_sum:
            max_sum = curr
            start, end = temp_start, i
    return max_sum, nums[start:end+1]

print(max_subarray_indices([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# (6, [4, -1, 2, 1])

Masalah Subtatasusunan Hasil Darab Maksimum

Masalah Subtatasusunan Hasil Darab Maksimum lebih rumit daripada varian jumlah kerana nombor negatif. Dua nombor negatif menghasilkan nombor positif apabila didarab, jadi hasil darab yang sangat negatif boleh menjadi maksimum selepas didarab dengan nombor negatif yang lain. Bagi [2, 3, -2, 4], jawapannya ialah 6 ([2, 3]). Bagi [-2, 0, -1], jawapannya ialah 0. Kita mesti menjejak kedua-dua hasil darab maksimum dan minimum pada setiap langkah.

nums = [2, 3, -2, 4]
# [2,3,-2,4]: products [2, 6, -12, -48]
# subarrays: [2]=2, [2,3]=6, [3]=3, etc.
# max is 6 from subarray [2,3]

nums2 = [-2, 3, -4]
# [-2]*3*[-4] = 24
# negative*negative=positive!
print('Expected:', 24)

Menjejak Kedua-dua Hasil Darab Maksimum dan Minimum

Wawasan utama ialah: pada setiap kedudukan, hasil darab maksimum semasa ialah salah satu daripada num, max_so_far * num atau min_so_far * num (yang terakhir membantu apabila nombor negatif menukar nilai minimum kepada maksimum). Begitu juga untuk nilai minimum. Kemas kini kedua-duanya, cur_max dan cur_min, secara serentak menggunakan nilai terdahulu supaya nilai yang telah dikemas kini tidak digunakan dalam langkah yang sama.

def max_product(nums):
    max_prod = min_prod = result = nums[0]
    for num in nums[1:]:
        # All three candidates for new max
        candidates = (num, max_prod * num, min_prod * num)
        max_prod, min_prod = max(candidates), min(candidates)
        result = max(result, max_prod)
    return result

print(max_product([2, 3, -2, 4]))    # 6
print(max_product([-2, 3, -4]))      # 24
print(max_product([-2, 0, -1]))      # 0
print(max_product([-2]))             # -2

Mengapa min_prod Penting

Pertimbangkan [-3, -10, 5]. Selepas memproses -3: max=-3, min=-3. Selepas -10: calon ialah (-10, 30, 30) → max=30, min=-10. Selepas 5: calon ialah (5, 150, -50) → max=150. Tanpa menjejak min_prod, anda akan terlepas perubahan yang berlaku apabila nilai minimum yang sangat negatif didarab dengan nombor negatif yang lain. Sentiasa kira kedua-dua max dan min daripada nilai terdahulu yang sama untuk mengelakkan pepijat pembacaan lapuk.

def max_product_traced(nums):
    max_p = min_p = result = nums[0]
    for num in nums[1:]:
        prev_max, prev_min = max_p, min_p
        max_p = max(num, prev_max * num, prev_min * num)
        min_p = min(num, prev_max * num, prev_min * num)
        result = max(result, max_p)
        print(f'num={num}: max_p={max_p}, min_p={min_p}')
    return result

max_product_traced([-3, -10, 5])
# max_p after -10: 30 (flip!)
# max_p after 5: 150

Sifar Menetapkan Semula Hasil Darab

Sifar dalam tatasusunan menetapkan semula kedua-dua hasil darab terkumpul kepada sifar, sekali gus membahagikan tatasusunan kepada subtatasusunan bebas. Apabila num = 0, kedua-dua max_prod * 0 = 0 dan min_prod * 0 = 0, maka ketiga-tiga calon menjadi 0 dan hasil maksimum terdahulu dikekalkan. Tiada kod kes khas diperlukan — formula umum mengendalikan sifar secara semula jadi.

def max_product(nums):
    max_p = min_p = result = nums[0]
    for num in nums[1:]:
        cands = (num, max_p * num, min_p * num)
        max_p, min_p = max(cands), min(cands)
        result = max(result, max_p)
    return result

# Zero splits array into independent subarrays
print(max_product([3, -1, 4, 0, 2, 5, -1]))   # 10 (2*5)
print(max_product([0, 2]))                       # 2
print(max_product([-1, 0, -2]))                  # 0

Alternatif: Imbasan Hasil Darab Kiri ke Kanan dan Kanan ke Kiri

Pendekatan alternatif mengimbas dari kiri ke kanan dan kanan ke kiri, dengan menetapkan semula hasil darab terkumpul kepada 1 apabila menemui sifar. Subtatasusunan hasil darab maksimum tidak pernah merentasi sifar, jadi jika nombor negatif menghasilkan keadaan buruk dalam satu arah, imbasan songsang akan menangkap perubahan itu. Pendekatan ini kemas, tetapi kaedah penjejakan minimum/maksimum lebih lazim dijangka dalam temu duga.

def max_product_sweep(nums):
    result = max(nums)
    left = right = 1
    n = len(nums)
    for i in range(n):
        left *= nums[i]
        right *= nums[n - 1 - i]
        result = max(result, left, right)
        if left == 0: left = 1
        if right == 0: right = 1
    return result

print(max_product_sweep([2, 3, -2, 4]))   # 6
print(max_product_sweep([-2, 3, -4]))     # 24
print(max_product_sweep([-2, 0, -1]))     # 0

Kadane berbanding Hasil Darab: Perbezaan Utama

Subtatasusunan jumlah dan hasil darab berbeza dalam beberapa cara penting. Bagi jumlah, nombor negatif sentiasa memudaratkan, jadi anda memulakan semula secara tamak. Bagi hasil darab, dua nombor negatif membantu, jadi anda perlu menjejak kedua-dua nilai ekstrem. Selain itu, sifar menamatkan hasil darab tetapi hanya sedikit memudaratkan jumlah. Apabila menerangkan dalam temu duga, nyatakan perbezaan ini dengan jelas dan jelaskan mengapa penjejakan nilai minimum diperlukan sebelum menulis sebarang kod.

# Max Sum Subarray: O(n) time, O(1) space
def max_sum(nums):
    curr = result = nums[0]
    for n in nums[1:]:
        curr = max(n, curr + n)  # restart or extend
        result = max(result, curr)
    return result

# Max Product Subarray: O(n) time, O(1) space
def max_prod(nums):
    lo = hi = result = nums[0]
    for n in nums[1:]:
        lo, hi = min(n, lo*n, hi*n), max(n, lo*n, hi*n)
        result = max(result, hi)
    return result

print(max_sum([-2, 1, -3, 4, -1, 2, 1]))   # 6
print(max_prod([-2, 3, -4]))               # 24

Kerumitan dan Petua Temu Duga

Kedua-dua algoritma Kadane (jumlah maksimum) dan penjejakan minimum/maksimum (hasil darab maksimum) berjalan dalam masa O(n) dan menggunakan ruang O(1). Petua temu duga utama: (1) Bagi jumlah maksimum, nyatakan alternatif Bahagi dan Takluk O(n log n) untuk menunjukkan keluasan pengetahuan. (2) Bagi hasil darab maksimum, tekankan bahawa anda mengemas kini min_prod dan max_prod secara serentak daripada nilai terdahulu supaya data lapuk tidak digunakan. (3) Sentiasa jelaskan: bolehkah tatasusunan kosong? Mestikah subtatasusunan tidak kosong? (Ya, mengikut kebiasaan, subtatasusunan mestilah tidak kosong.)

# Both run O(n) time, O(1) space
# Kadane handles: all negative (returns least negative)
# Product handles: zeros (resets naturally), negatives (tracks both extremes)

nums_all_neg = [-5, -2, -8]
print('Max sum (all neg):', max(max(nums_all_neg[0:1]),
      max(x for x in nums_all_neg)))  # -2
# Correct: return the maximum element when all are negative

Semakan Ringkas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Imbas Kembali Pelajaran

Dalam pelajaran ini anda telah mempelajari: algoritma Kadane menyelesaikan subtatasusunan jumlah maksimum dalam O(n) dengan memilih sama ada memanjangkan atau memulakan semula pada setiap elemen, subtatasusunan hasil darab maksimum memerlukan penjejakan kedua-dua hasil darab terkumpul minimum dan maksimum kerana perubahan tanda yang disebabkan oleh nombor negatif, dan sifar menetapkan semula hasil darab terkumpul secara semula jadi tanpa kod kes khas. Seterusnya, kita akan meneroka masalah Pemisahan Perkataan menggunakan jadual DP satu dimensi.

Percuma untuk bermula

Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 90
Pelajaran: 360

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Subtatasusunan Maksimum dan Subtatasusunan Hasil Darab Maksimum” percuma?

Ya — teks penuh “Subtatasusunan Maksimum dan Subtatasusunan Hasil Darab Maksimum” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Subtatasusunan Maksimum dan Subtatasusunan Hasil Darab Maksimum”?

Gunakan algoritma Kadane pada maximum-sum-subarray dan lanjutkannya untuk menjejaki nilai maksimum serta minimum bagi variasi hasil darab. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?

Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.

Berapa lamakah pelajaran “Subtatasusunan Maksimum dan Subtatasusunan Hasil Darab Maksimum” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?

Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

House Robber: Pengulangan Ambil atau Langkau
Subtatasusunan Maksimum dan Subtatasusunan Hasil Darab Maksimum
Pemisahan Perkataan dan Pembahagian Rentetan
Menyahkod Cara dan Mengira Laluan

← Kembali ke Persediaan Temu Duga Pengaturcaraan