Longest Increasing Subsequence

Q: Apa kompleksitas waktu dari Longest Increasing Subsequence?

method tails berjalan dalam waktu O(n log n) dan ruang O(n) : satu pencarian biner untuk setiap elemen. Tabel untuk setiap pasangan indeks membutuhkan waktu O(n²) , dan mencoba setiap subsequence membutuhkan O(2ⁿ) .

SedangDynamic programming Binary search

+10

Kamu mendapatkan list bilangan bulat nums. Subsekuens mempertahankan beberapa elemen dalam urutan aslinya dan membuang sisanya; elemen yang dipertahankan tidak harus bersebelahan. Kembalikan panjang subsekuens terpanjang dengan nilai yang meningkat secara ketat dari kiri ke kanan. Dua nilai yang sama secara berurutan tidak dihitung sebagai meningkat.

Fungsi

lengthOfLIS(nums: integer-array) → integer

numsinteger-array: daftar bilangan bulat untuk dipilih
Mengembalikaninteger: panjang subsekuens meningkat ketat terpanjang

Batasan

1 ≤ nums.length ≤ 2500
-10⁴ ≤ nums[i] ≤ 10⁴

Contoh

Input: nums = [3, 1, 8, 2, 5, 9, 4, 7]
Output: 4
Penjelasan: 1, 2, 5, 9 terus meningkat, begitu juga 1, 2, 5, 7 dan 1, 2, 4, 7: panjangnya 4. Tidak ada pilihan lima nilai yang terus meningkat.

Pertanyaan lanjutan

Bisakah kamu mengembalikan salah satu subsekuens menaik terpanjang itu sendiri, beserta panjangnya, dan tetap berjalan dalam waktu O(n log n)?

Petunjuk

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

0 dari 3 dibuka

Solusi

List berisi n angka memiliki 2^n subsekuens, terlalu banyak untuk diperiksa. Jika kita menanyakan, untuk setiap indeks, berapa panjang subsekuens menaik terbaik yang berakhir tepat di sana, kita mendapatkan tabel O(n²). Versi tercepat menyimpan, untuk setiap panjang, nilai terkecil yang dapat menjadi nilai akhir subsekuens dengan panjang tersebut, lalu menempatkan setiap elemen menggunakan pencarian biner.

Ambil atau lewati setiap elemen

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Tentukan untuk setiap elemen apakah akan mempertahankannya; kamu boleh mempertahankan nums[i] hanya jika nilainya lebih besar daripada nilai terakhir yang dipertahankan. longest(i, prev) adalah jumlah elemen terbanyak yang masih bisa kamu tambahkan mulai dari indeks i, ketika elemen terakhir yang dipertahankan berada di prev (atau -1). Melewati elemen menghasilkan longest(i+1, prev); mempertahankannya menghasilkan 1 + longest(i+1, i). Setiap subsekuens meningkat adalah satu jalur dari pilihan-pilihan ini.

Pada 1, 2, 3, ..., n, kedua cabang tetap terbuka dan jumlah pemanggilan berlipat ganda untuk setiap elemen: 2^40 sudah sekitar 10^12. Namun, ada paling banyak n² pasangan berbeda (i, prev).

Algoritma

Tulis longest(i, prev), dengan prev sebagai indeks elemen terakhir yang dipertahankan, atau -1.
Jika i melewati akhir, kembalikan 0.
Lewati nums[i]: best = longest(i+1, prev).
Jika prev adalah -1 atau nums[i] > nums[prev], pertahankan elemen tersebut: best = max(best, 1 + longest(i+1, i)).
Kembalikan best. Jawabannya adalah longest(0, -1).

def lengthOfLIS(nums):
    def longest(i, prev):
        # The longest increasing subsequence of nums[i:] whose values all exceed nums[prev].
        # prev is -1 while nothing has been taken.
        if i == len(nums):
            return 0
        best = longest(i + 1, prev)  # skip nums[i]
        if prev == -1 or nums[i] > nums[prev]:
            best = max(best, 1 + longest(i + 1, i))  # take nums[i]
        return best

    return longest(0, -1)

Suburutan terpanjang yang berakhir pada setiap indeks

Intuisi

Misalkan ending[i] adalah panjang subsekuens meningkat terpanjang yang elemen terakhirnya adalah nums[i]. Jika ada, elemen sebelum nums[i] adalah nums[j] dengan j < i dan nums[j] < nums[i], dan bagian hingga elemen itu harus sepanjang mungkin. Jadi, ending[i] = 1 + max(ending[j]) untuk semua j tersebut, atau 1 jika tidak ada. Isi nilainya dari kiri ke kanan.

Untuk [3, 1, 8, 2, 5, 9, 4, 7], tabelnya adalah [1, 1, 2, 2, 3, 4, 3, 4]: 5 dapat mengikuti 3, 1, atau 2, dan yang terbaik di antaranya memiliki panjang 2, jadi ending[4] = 3. Jawabannya adalah nilai terbesar, karena subsekuens terbaik dapat berakhir di mana saja.

n(n-1)/2 perbandingan: sekitar 3.1 × 10^6 untuk n = 2500.

Algoritma

Buat ending dengan setiap entri bernilai 1.
Untuk setiap i dari kiri ke kanan, periksa setiap j < i.
Jika nums[j] < nums[i], atur ending[i] menjadi ending[j] + 1 jika nilainya lebih besar.
Kembalikan nilai terbesar dalam ending.

def lengthOfLIS(nums):
    n = len(nums)
    # ending[i]: the longest increasing subsequence that ends with nums[i]
    ending = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i] and ending[j] + 1 > ending[i]:
                ending[i] = ending[j] + 1
    return max(ending)

Ekor terkecil dengan pencarian biner

Intuisi

Untuk setiap panjang, simpan hanya nilai terkecil yang dapat menjadi nilai akhir subsekuens menaik dengan panjang tersebut: tails[k] untuk panjang k+1. Nilai akhir yang lebih kecil tidak pernah lebih buruk: apa pun yang bisa mengikuti 9 juga bisa mengikuti 5. tails selalu meningkat secara ketat: hilangkan nilai terakhir dari subsekuens menaik dengan panjang k+2, lalu kamu mendapatkan subsekuens dengan panjang k+1 yang berakhir dengan nilai lebih kecil.

Untuk setiap x, lakukan pencarian biner untuk menemukan nilai akhir pertama yang ≥ x. Jika tidak ada, tambahkan x: ini memperpanjang subsekuens terpanjang. Jika ada, ganti nilai akhir tersebut dengan x: subsekuens yang panjangnya kurang satu berakhir dengan nilai di bawah x, jadi x menghasilkan panjang yang sama dengan nilai akhir yang lebih kecil.

Untuk contoh 1, tails menjadi [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7]: panjangnya 4. Dalam [1, 2, 4, 9], nilai 4 muncul setelah 9, jadi hanya panjang tails yang bermakna.

Algoritma

Mulai dengan list kosong tails.
Untuk setiap x dalam nums, lakukan pencarian biner untuk indeks pertama k dengan tails[k] ≥ x.
Jika tidak ada tail yang ≥ x, tambahkan x.
Jika tidak, atur tails[k] = x.
Kembalikan panjang tails.

from bisect import bisect_left


def lengthOfLIS(nums):
    # tails[k]: the smallest last value of any increasing subsequence of length k + 1
    tails = []
    for x in nums:
        k = bisect_left(tails, x)  # the first tail that is >= x
        if k == len(tails):
            tails.append(x)  # x extends the longest subsequence so far
        else:
            tails[k] = x  # x is a smaller ending for length k + 1
    return len(tails)

Jebakan dan kasus tepi

Mengembalikan ending[n-1] alih-alih entri terbesar. Untuk [1, 2, 3, 0], entri terakhir adalah 1, tetapi jawabannya 3.
Membandingkan dengan ≤ alih-alih <. [7, 7, 7, 7] harus mengembalikan 1, bukan 4.
Dalam versi tails, mencari tail pertama yang > x alih-alih ≥ x. Angka 7 yang kedua kemudian ditambahkan setelah angka pertama, sehingga nilai yang sama dihitung sebagai meningkat.
Keliru menyelesaikan versi berurutan. Dalam contoh 1, rangkaian naik terpanjang dari elemen yang bersebelahan adalah 2, 5, 9 (panjang 3), sedangkan jawabannya 4.
Tetap menggunakan indeks berbasis 0 di Lua atau R, padahal array dimulai dari 1. Penanda prev = -1 menjadi 0, dan pencarian biner berjalan pada indeks 1 hingga ukuran saat ini.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Longest Increasing Subsequence?

method tails berjalan dalam waktu O(n log n) dan ruang O(n): satu pencarian biner untuk setiap elemen. Tabel untuk setiap pasangan indeks membutuhkan waktu O(n²), dan mencoba setiap subsequence membutuhkan O(2ⁿ).

Apa itu patience sorting dalam Longest Increasing Subsequence?

Ini adalah method tails yang dinamai berdasarkan permainan kartu. Setiap tails adalah kartu teratas dari sebuah tumpukan: sebuah kartu ditempatkan pada tumpukan paling kiri yang kartu teratasnya memiliki nilai setidaknya sebesar nilainya, atau memulai tumpukan baru. Jumlah tumpukan adalah jawabannya.

Bagaimana cara menemukan subsekuens tidak menurun yang terpanjang?

Izinkan elemen bertetangga bernilai sama. Pada tabel, gunakan nums[j] ≤ nums[i]. Dalam method tails, cari tail pertama yang nilainya lebih besar secara ketat dari x, sehingga nilai yang sama memperpanjang list alih-alih mengganti tail. Setelah itu, [7, 7, 7, 7] menghasilkan 4.

def lengthOfLIS(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [3, 1, 8, 2, 5, 9, 4, 7]

Output yang diharapkan

Longest Increasing Subsequence

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Ambil atau lewati setiap elemen

Suburutan terpanjang yang berakhir pada setiap indeks

Ekor terkecil dengan pencarian biner

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa