Maximum Subarray

+10

Kamu mendapatkan sebuah list bilangan bulat nums. Subarray adalah rangkaian elemen bersebelahan yang diambil tanpa jeda, dan harus berisi setidaknya satu elemen. Kembalikan jumlah terbesar yang bisa dimiliki subarray mana pun dari nums. Kamu hanya mengembalikan jumlahnya, bukan subarray itu sendiri.

Fungsi

maxSubArray(nums: integer-array) → integer

numsinteger-array: daftar bilangan bulat, dengan setidaknya satu elemen
Mengembalikaninteger: jumlah terbesar dari rangkaian elemen bersebelahan yang tidak kosong

Batasan

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴
Jawabannya selalu muat dalam bilangan bulat bertanda 32-bit.

Contoh

Input: nums = [2, -4, 3, -1, 5, -6, 1]
Output: 7
Penjelasan: Perulangan [3, -1, 5] berjumlah 7. Memperluasnya ke kiri menambahkan -4 lalu 2, sehingga totalnya berkurang 2. Memperluasnya ke kanan menambahkan -6 lalu 1, sehingga totalnya berkurang 5. Tidak ada perulangan lain yang hasilnya lebih baik.

Pertanyaan lanjutan

Bisakah kamu juga menyelesaikannya dengan strategi bagi dan taklukkan dalam O(n log n), membagi list menjadi dua dan menangani rangkaian yang melintasi bagian tengah?

Solusi

Sebuah list berisi n angka memiliki sekitar n²/2 subarray, terlalu banyak untuk diperiksa satu per satu jika ada 10^5 elemen. Bagian tersulit adalah angka negatif: suatu rangkaian harus mempertahankan elemen negatif jika angka setelahnya bisa mengimbanginya, dan membuang semua elemen sebelumnya jika tidak. Algoritma Kadane membuat pilihan itu pada setiap elemen dengan satu perbandingan.

Jumlahkan setiap subarray

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Setiap subarray memiliki indeks pertama left dan indeks terakhir right, jadi mencoba setiap pasangan akan menemukan yang terbaik. Tetapkan left lalu geser right ke depan, sambil menambahkan setiap elemen baru ke total yang terus diperbarui: setiap subarray hanya memerlukan satu penjumlahan, tanpa perulangan ketiga.

Namun, masih ada sekitar n²/2 pasangan, yaitu lima miliar penjumlahan untuk 10^5 elemen.

Algoritma

Atur best ke elemen pertama.
Untuk setiap indeks awal left, atur total yang terus diperbarui ke 0.
Pindahkan right dari left hingga akhir list, lalu tambahkan nums[right] ke total.
Setelah setiap penambahan, simpan total ke best jika nilainya lebih besar.
Kembalikan best.

def maxSubArray(nums):
    best = nums[0]
    for left in range(len(nums)):
        total = 0
        # Grow the subarray that starts at left by one element at a time
        for right in range(left, len(nums)):
            total += nums[right]
            best = max(best, total)
    return best

Algoritma Kadane

Intuisi

Rangkaian terbaik yang berakhir pada indeks i adalah nums[i] saja, atau rangkaian terbaik yang berakhir pada i-1 dengan menambahkan nums[i], karena tidak ada rangkaian lain yang berakhir pada i-1 dengan jumlah yang lebih besar. Jadi, simpan satu angka, endingHere, yaitu jumlah terbaik dari rangkaian yang berakhir pada elemen saat ini. Pada elemen berikutnya, x, nilainya menjadi yang lebih besar antara x dan endingHere + x: selama jumlah rangkaian positif, kamu memperpanjangnya, dan begitu jumlahnya nol atau negatif, kamu memulai lagi dari x.

Subarray terbaik berakhir di suatu tempat, jadi jawabannya adalah nilai terbesar yang dicapai endingHere. Pada contoh pertama, nilainya berturut-turut adalah 2, -2, 3, 2, 7, 1, 2, dan jawabannya adalah 7.

Algoritma

Atur endingHere dan best ke elemen pertama.
Untuk setiap elemen berikutnya x, atur endingHere ke nilai yang lebih besar antara x dan endingHere + x.
Atur best ke nilai yang lebih besar antara best dan endingHere.
Setelah elemen terakhir, kembalikan best.

def maxSubArray(nums):
    current = nums[0]
    best = nums[0]
    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])
        best = max(best, current)
    return best

Jebakan dan kasus tepi

Memulai best dari 0. [-3, -1, -2] kemudian menghasilkan 0, bukan -1. Mulailah dari elemen pertama.
Membatasi jumlah sementara dengan max(0, endingHere + x). Cara ini gagal pada list yang sama; bandingkan dengan x.
Menjumlahkan hanya angka positif. Elemen-elemen tersebut harus bersebelahan, jadi contoh pertama menghasilkan 7, bukan 2 + 3 + 5 + 1 = 11.
Memulai perulangan pada indeks 1 tanpa menetapkan endingHere dan best ke nums[0]. List yang hanya memiliki satu elemen, seperti [-5], harus menghasilkan -5.

Pertanyaan yang sering diajukan3

Apa itu algoritma Kadane?

Algoritma Kadane menemukan jumlah terbesar dari subarray berurutan dalam satu kali lintasan. Algoritma ini menyimpan jumlah terbaik dari rangkaian yang berakhir pada elemen saat ini dan, pada setiap elemen baru, memilih untuk melanjutkan rangkaian tersebut atau memulai rangkaian baru. Jumlah terbesar dari nilai-nilai ini adalah jawabannya.

Berapa kompleksitas waktu dari Maximum Subarray?

Algoritma Kadane membutuhkan waktu O(n) dan ruang tambahan O(1), karena setiap elemen diperiksa satu kali. Memeriksa setiap subarray dengan total berjalan membutuhkan O(n²), sedangkan menjumlahkan setiap subarray dari awal membutuhkan O(n³).

Mengapa Maximum Subarray merupakan masalah pemrograman dinamis?

Jumlah terbaik dari perulangan yang berakhir pada indeks i hanya bergantung pada jumlah terbaik dari perulangan yang berakhir pada i-1. Ini adalah relasi rekurensi atas indeks, ciri khas pemrograman dinamis. Algoritma Kadane hanya menyimpan nilai terbaru, bukan seluruh tabel, sehingga hanya membutuhkan ruang O(1).

def maxSubArray(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

nums = [2, -4, 3, -1, 5, -6, 1]

Output yang diharapkan