Longest Increasing Subsequence (LIS) adalah masalah klasik dengan dua solusi berbeda: DP O(n²) yang natural, dan O(n log n) dengan binary search yang elegan. Selain panjang, kita sering ingin merekonstruksi subsequence itu sendiri. LIS muncul di banyak aplikasi: scheduling, analisis sequence, dan persoalan geometri. Pada Chapter ini kita akan membedah kedua pendekatan, algoritma patience sorting, dan rekonstruksi.

Aturan: Subsequence Naik Terpanjang #

Diberikan array a[0..n-1], cari subsequence terpanjang (tidak harus contiguous) sehingga setiap elemen lebih besar dari elemen sebelumnya. Variasi umum: “strictly increasing” (a[i] < a[j]) atau “non-decreasing” (a[i] <= a[j]).

Mekanisme 1: DP O(n²) #

State: dp[i] = panjang LIS yang berakhir tepat di indeks i.

Recurrence:

text 
dp[i] = 1 + max(dp[j] for j < i if a[j] < a[i])
       (jika tidak ada j valid, dp[i] = 1)

Setiap dp[i] adalah best dari semua predecessor valid yang lebih kecil dari a[i], ditambah 1 untuk elemen i itu sendiri.

Jawaban: max(dp[i] for i = 0..n-1).

Kode: DP O(n²) #

cpp 
#include <iostream>
#include <vector>
#include <algorithm>

int lis_dp(const std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    if (n == 0) return 0;
    std::vector<int> dp(n, 1);
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (a[j] < a[i]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }
    return *std::max_element(dp.begin(), dp.end());
}

int main() {
    std::vector<int> a = {3, 10, 2, 1, 20};
    std::cout << "LIS length = " << lis_dp(a) << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
LIS length = 3
  1. Baris std::vector<int> dp(n, 1);: setiap elemen sendiri adalah LIS sepanjang 1. Base case implisit.
  2. Baris for (int j = 0; j < i; ++j): cek semua predecessor j dari i.
  3. Baris if (a[j] < a[i]): syarat — predecessor harus lebih kecil (strictly increasing).
  4. Baris dp[i] = std::max(dp[i], dp[j] + 1);: perpanjang LIS yang berakhir di j dengan elemen i.
  5. Hasil 3: LIS {3, 10, 20} atau {2, ...} → panjang 3.

Rekonstruksi LIS (O(n²)) #

cpp 
#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> lis_reconstruct(const std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    if (n == 0) return {};
    std::vector<int> dp(n, 1), parent(n, -1);
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
    }
    int best_end = static_cast<int>(
        std::max_element(dp.begin(), dp.end()) - dp.begin());
    std::vector<int> result;
    int cur = best_end;
    while (cur != -1) {
        result.push_back(a[cur]);
        cur = parent[cur];
    }
    std::reverse(result.begin(), result.end());
    return result;
}

int main() {
    std::vector<int> a = {3, 10, 2, 1, 20};
    auto seq = lis_reconstruct(a);
    std::cout << "LIS = ";
    for (int x : seq) std::cout << x << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
LIS = 3 10 20
  1. Baris std::vector<int> dp(n, 1), parent(n, -1);: tambahkan array parent untuk traceback. parent[i] menyimpan indeks predecessor terbaik.
  2. Baris parent[i] = j;: catat predecessor setiap kali dp[i] diperbarui.
  3. Baris while (cur != -1): mulai dari best_end (indeks dengan dp maksimum), ikuti parent hingga ke awal.
  4. Hasil 3 10 20: salah satu LIS yang valid.

Mekanisme 2: Patience Sorting O(n log n) #

Ide kunci: maintain array tails[k] = elemen akhir terkecil yang bisa dicapai oleh LIS sepanjang k+1. Untuk setiap elemen a[i], lakukan binary search di tails untuk menemukan posisi a[i].

  • Bila a[i] lebih besar dari semua tails, append — LIS bertambah panjang.
  • Bila tidak, ganti elemen pertama di tails yang >= a[i] dengan a[i] — ini menjaga tails tetap minimal tanpa mengubah panjang LIS.

Panjang tails = panjang LIS. Catatan: tails itu sendiri bukan selalu LIS yang valid, hanya panjangnya yang benar.

Kode: Patience Sorting O(n log n) #

cpp 
#include <iostream>
#include <vector>
#include <algorithm>

int lis_fast(const std::vector<int>& a) {
    std::vector<int> tails;
    for (int x : a) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }
    return static_cast<int>(tails.size());
}

int main() {
    std::vector<int> a = {3, 10, 2, 1, 20};
    std::cout << "LIS fast = " << lis_fast(a) << '\n';

    std::vector<int> b = {10, 9, 2, 5, 3, 7, 101, 18};
    std::cout << "LIS fast = " << lis_fast(b) << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
LIS fast = 3
LIS fast = 4
  1. Baris auto it = std::lower_bound(tails.begin(), tails.end(), x);: cari elemen pertama di tails yang >= x. Kompleksitas O(log k).
  2. Baris if (it == tails.end()) tails.push_back(x);: bila x lebih besar dari semua, perpanjang LIS.
  3. Baris *it = x;: ganti elemen pertama yang >= x dengan x. Ini menjaga tails tetap minimal, sehingga peluang perpanjangan di masa depan meningkat.
  4. Hasil 3 untuk {3,10,2,1,20}: LIS {3,10,20} atau {2,...}.
  5. Hasil 4 untuk {10,9,2,5,3,7,101,18}: LIS {2,5,7,101} atau {2,3,7,18}.

Rekonstruksi LIS dengan O(n log n) #

Untuk merekonstruksi, simpan indeks ke tails setiap kali update, lalu traceback:

cpp 
#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> lis_fast_reconstruct(const std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    if (n == 0) return {};
    std::vector<int> tails, tails_idx, parent(n, -1);
    for (int i = 0; i < n; ++i) {
        auto it = std::lower_bound(tails.begin(), tails.end(), a[i]);
        int pos = static_cast<int>(it - tails.begin());
        if (it == tails.end()) {
            tails.push_back(a[i]);
            tails_idx.push_back(i);
        } else {
            *it = a[i];
            tails_idx[pos] = i;
        }
        parent[i] = (pos > 0) ? tails_idx[pos - 1] : -1;
    }
    // Traceback
    std::vector<int> result;
    int cur = tails_idx.back();
    while (cur != -1) {
        result.push_back(a[cur]);
        cur = parent[cur];
    }
    std::reverse(result.begin(), result.end());
    return result;
}

int main() {
    std::vector<int> a = {10, 9, 2, 5, 3, 7, 101, 18};
    auto seq = lis_fast_reconstruct(a);
    std::cout << "LIS = ";
    for (int x : seq) std::cout << x << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
LIS = 2 3 7 18
  1. Baris tails_idx.push_back(i);: simpan indeks elemen yang menjadi ekor tails.
  2. Baris parent[i] = (pos > 0) ? tails_idx[pos - 1] : -1;: predecessor adalah ekor tails sebelum posisi pos. Inilah elemen yang menjadi “basis” untuk a[i].
  3. Baris int cur = tails_idx.back();: mulai dari ekor terakhir — ini pasti elemen akhir dari sebuah LIS.
  4. Hasil 2 3 7 18: LIS yang valid.

Variasi #

VariasiModifikasi
Non-decreasing (mengizinkan sama)Ganti lower_bound dengan upper_bound
Longest decreasingNegasi elemen, lalu LIS
2D LIS (Russian doll)Sortir satu dimensi, lalu LIS pada dimensi lain
Count number of LISTambahkan array count[] untuk menghitung cara mencapai panjang tertentu

Tabel Kompleksitas #

PendekatanWaktuRuangRekonstruksi
DP O(n²)O(n²)O(n)Mudah dengan parent[]
Patience sortingO(n log n)O(n)Perlu tails_idx + parent[]

Ringkasan #

  • LIS O(n²): state dp[i] = LIS berakhir di i, transisi 1 + max(dp[j]) untuk j < i yang a[j] < a[i].
  • LIS O(n log n) dengan patience sorting: maintain tails[k] = ekor minimum LIS sepanjang k+1.
  • Rekonstruksi: simpan parent[] untuk traceback.
  • Variasi: non-decreasing (pakai upper_bound), decreasing (negasi), 2D (sortir lalu LIS).
  • Pilih DP O(n²) bila n kecil dan butuh kesederhanaan; pakai patience sorting untuk n besar.