Najdłuższy rosnący podciąg (LIS)

Wprowadzenie

Najdłuższy rosnący podciąg (ang. Longest Increasing Subsequence, LIS) to klasyczny problem optymalizacyjny w informatyce. Ma szerokie zastosowanie w: - Analizie trendów i danych czasowych - Optymalizacji procesów - Problemach pasjansa (np. Patience Sorting) - Algorytmach graficznych (np. planowanie zadań) - Teorii gier i strategii

Definicja problemu

Dany: - Ciąg liczb arr = [a₁, a₂, ..., aₙ]

Znajdź: - Najdłuższy podciąg (niekoniecznie ciągły), w którym każdy element jest większy od poprzedniego

Przykład:

arr = [10, 9, 2, 5, 3, 7, 101, 18]

Rosnące podciągi:
- [2, 5, 7, 101]  ← długość 4
- [2, 5, 7, 18]   ← długość 4
- [2, 3, 7, 18]   ← długość 4
- [2, 3, 7, 101]  ← długość 4

LIS = 4 (jeden z powyższych)

Uwaga: Podciąg może być: - Ściśle rosnący (strictly increasing): a[i] < a[j] dla i < j - Niemalejący (non-decreasing): a[i] ≤ a[j] dla i < j

W tej lekcji skupimy się na ściśle rosnącym.

Różnica: Podciąg vs Podtablica

Przypomnienie:

Ciąg: [3, 10, 2, 1, 20]

Podciąg: [3, 10, 20] ✅ (elementy nieciągłe, zachowana kolejność)
Podtablica: [10, 2, 1] ✅ (elementy MUSZĄ być ciągłe)

[3, 20, 10] ❌ (zmieniona kolejność - nie jest podciągiem)
[3, 2, 20] ✅ (podciąg, ale NIE podtablica)

Problem LIS dotyczy PODCIĄGÓW (nieciągłych).

Podejście 1: Rekurencja naiwna

Wzór rekurencyjny

Dla każdego elementu arr[i] mamy dwa wybory: 1. Włączyć arr[i] do LIS (jeśli arr[i] > ostatni element w LIS) 2. Pominąć arr[i]

LIS(arr, n, prev) =
    0                                    jeśli n = 0
    max(
        LIS(arr, n-1, prev),            // Pomijamy arr[n-1]
        1 + LIS(arr, n-1, arr[n-1])     // Bierzemy arr[n-1] (jeśli arr[n-1] > prev)
    )

Implementacja rekurencyjna

Problem: Wykładnicza złożoność - za wolne dla n > 20.

Podejście 2: Programowanie dynamiczne O(n²)

Wzór DP

Definiujemy dp[i] jako długość najdłuższego rosnącego podciągu kończącego się na pozycji i.

dp[i] = max(dp[j] + 1) dla wszystkich j < i, gdzie arr[j] < arr[i]
dp[i] = 1 jeśli żadne j nie spełnia warunku (arr[i] jest początkiem nowego LIS)

Wynik końcowy: max(dp[0], dp[1], ..., dp[n-1])

Implementacja O(n²)

Krok po kroku:

arr = [10, 9, 2, 5, 3, 7, 101, 18]

Inicjalizacja:
dp = [1, 1, 1, 1, 1, 1, 1, 1]

i=1 (arr[1]=9):
  j=0: arr[0]=10 > 9 → nie rozszerzamy
  dp[1] = 1

i=2 (arr[2]=2):
  j=0: 10 > 2 → nie
  j=1: 9 > 2 → nie
  dp[2] = 1

i=3 (arr[3]=5):
  j=0: 10 > 5 → nie
  j=1: 9 > 5 → nie
  j=2: 2 < 5 → dp[3] = max(1, dp[2]+1) = 2 ✓
  dp[3] = 2

i=4 (arr[4]=3):
  j=0,1: nie
  j=2: 2 < 3 → dp[4] = max(1, 1+1) = 2 ✓
  j=3: 5 > 3 → nie
  dp[4] = 2

i=5 (arr[5]=7):
  j=2: 2 < 7 → dp[5] = max(1, 1+1) = 2
  j=3: 5 < 7 → dp[5] = max(2, 2+1) = 3 ✓
  j=4: 3 < 7 → dp[5] = max(3, 2+1) = 3
  dp[5] = 3

i=6 (arr[6]=101):
  ...podobnie...
  dp[6] = 4 (rozszerzając LIS kończący się na 7)

i=7 (arr[7]=18):
  ...
  dp[7] = 4

Wynik końcowy:
dp = [1, 1, 1, 2, 2, 3, 4, 4]
max(dp) = 4

Rekonstrukcja LIS (O(n²))

Podejście 3: Algorytm optymalny O(n log n)

Idea: Patience Sorting

Kluczowa obserwacja: - Chcemy utrzymywać końce potencjalnych LIS o różnych długościach - Dla każdego nowego elementu, zastępujemy najmniejszy końcowy element większy lub równy nowemu elementowi

Algorytm: 1. Utrzymuj tablicę tails, gdzie tails[i] = najmniejszy końcowy element LIS długości i+1 2. Dla każdego elementu arr[i]: - Znajdź pozycję w tails używając wyszukiwania binarnego - Zaktualizuj tails na tej pozycji

Dlaczego to działa? - tails jest zawsze posortowana - Długość tails = długość aktualnego LIS

Implementacja O(n log n)

Krok po kroku:

arr = [10, 9, 2, 5, 3, 7, 101, 18]

Początek: tails = []

num=10:
  pos = bisect_left([], 10) = 0
  pos == len(tails) → append
  tails = [10]

num=9:
  pos = bisect_left([10], 9) = 0
  Zastąp tails[0] = 9
  tails = [9]

num=2:
  pos = bisect_left([9], 2) = 0
  Zastąp tails[0] = 2
  tails = [2]

num=5:
  pos = bisect_left([2], 5) = 1
  pos == len(tails) → append
  tails = [2, 5]

num=3:
  pos = bisect_left([2, 5], 3) = 1
  Zastąp tails[1] = 3
  tails = [2, 3]

num=7:
  pos = bisect_left([2, 3], 7) = 2
  pos == len(tails) → append
  tails = [2, 3, 7]

num=101:
  pos = bisect_left([2, 3, 7], 101) = 3
  pos == len(tails) → append
  tails = [2, 3, 7, 101]

num=18:
  pos = bisect_left([2, 3, 7, 101], 18) = 3
  Zastąp tails[3] = 18
  tails = [2, 3, 7, 18]

Długość LIS = len(tails) = 4

Uwaga: tails NIE JEST samym LIS, ale jego długość = długość LIS!

Rekonstrukcja LIS (O(n log n))

Uwaga: Rekonstrukcja pełnej sekwencji w O(n log n) jest technicznie możliwa, ale bardziej skomplikowana. W praktyce często używamy algorytmu O(n²) do rekonstrukcji, a O(n log n) tylko do obliczenia długości.

Warianty problemu LIS

1. Najdłuższy niemalejący podciąg (LDS)

2. Najdłuższy malejący podciąg

3. Liczba LIS

Znajdź liczbę różnych LIS o maksymalnej długości.

Benchmark: Porównanie O(n²) vs O(n log n)

Przykładowe wyniki:

n=15:
  Rekurencja      → czas: 0.002341s, długość LIS: 6
  DP O(n²)        → czas: 0.000021s, długość LIS: 6
  O(n log n)      → czas: 0.000015s, długość LIS: 6

n=100:
  DP O(n²)        → czas: 0.001234s, długość LIS: 12
  O(n log n)      → czas: 0.000089s, długość LIS: 12

n=1000:
  DP O(n²)        → czas: 0.123456s, długość LIS: 32
  O(n log n)      → czas: 0.001234s, długość LIS: 32

n=10000:
  DP O(n²)        → czas: 12.345678s, długość LIS: 98
  O(n log n)      → czas: 0.023456s, długość LIS: 98

Wnioski:
- Dla n=10000: O(n log n) jest ~500× szybsze!
- Różnica rośnie wraz z n

Praktyczne zastosowania LIS

1. Analiza trendów giełdowych

Wyjście:

Najdłuższy okres wzrostowy: 5 dni
Dni i ceny:
  Dzień 1: 80 zł
  Dzień 2: 90 zł
  Dzień 4: 95 zł
  Dzień 5: 110 zł
  Dzień 7: 120 zł

2. Planowanie zadań z zależnościami

3. Pasjans (Patience Sorting)

Wyjście:

Liczba stosów: 4
Stosy:
  Stos 1: [10, 9, 2]
  Stos 2: [5, 3]
  Stos 3: [7]
  Stos 4: [101, 18]

Minimalna liczba stosów (= długość LIS): 4

Podsumowanie algorytmów LIS

Algorytm	Złożoność czasowa	Złożoność pamięciowa	Rekonstrukcja	Uwagi
Rekurencja naiwna	O(2^n)	O(n)	Trudna	Za wolne dla n > 20
DP O(n²)	O(n²)	O(n)	✅ Prosta	Dobry dla n ≤ 5000
O(n log n)	O(n log n)	O(n)	Możliwa (złożona)	Najszybszy, zalecany dla n > 5000

Porównanie: LCS vs LIS

Cecha	LCS	LIS
Typ danych	Dwie sekwencje	Jedna sekwencja
Warunek	Elementy wspólne	Elementy rosnące
Złożoność DP	O(m·n)	O(n²) lub O(n log n)
Zastosowania	Diff, plagiat, DNA	Trendy, optymalizacja, pasjans

Co dalej?

Po opanowaniu problemu LIS, następne kroki to:

Inne problemy DP na sekwencjach:
Maximum Subarray (Kadane's Algorithm)
Edit Distance (Levenshtein Distance)
Longest Palindromic Subsequence
Zaawansowane problemy kombinatoryczne:
Matrix Chain Multiplication
Rod Cutting Problem
Partition Problem
Algorytmy grafowe z DP:
Shortest Path (Bellman-Ford, Floyd-Warshall)
Traveling Salesman Problem (TSP)
Longest Path in DAG
Struktury danych zaawansowane:
Segment Trees
Fenwick Trees (Binary Indexed Trees)
Suffix Arrays i Suffix Trees

Zadania praktyczne

Zadanie 1: Liczba usunięć

Oblicz minimalną liczbę usunięć, aby ciąg stał się rosnący. Odpowiedź: n - LIS(arr).

Zadanie 2: Longest Bitonic Subsequence

Znajdź najdłuższy podciąg, który najpierw rośnie, potem maleje. Wskazówka: LIS od początku + LDS od końca.

Zadanie 3: Wizualizacja

Stwórz wizualizację algorytmu O(n log n) pokazującą, jak zmienia się tablica tails.

Zadanie 4: LIS z wagami

Każdy element ma wagę. Znajdź rosnący podciąg o maksymalnej sumie wag (niekoniecznie najdłuższy).

Podsumowanie kursu programowania dynamicznego

Gratulacje! Ukończyłeś kurs o programowaniu dynamicznym. Poznałeś:

Lekcja 46: Wprowadzenie do DP - optymalna podstruktura, nakładające się podproblemy
Lekcja 47: Memoization - top-down DP, @lru_cache
Lekcja 48: Tabulation - bottom-up DP, optymalizacja pamięci
Lekcje 49-51: Problem plecaka - analiza, zachłanny, DP
Lekcja 52: LCS - porównywanie sekwencji, diff, bioinformatyka
Lekcja 53: LIS - trendy, optymalizacja, O(n log n)

Kluczowe techniki: - Identyfikacja optymalnej podstruktury - Definiowanie stanów DP - Wzory rekurencyjne i tabelaryczne - Optymalizacja pamięci (2D → 1D) - Rekonstrukcja rozwiązań (backtracking) - Wybór między memoization a tabulation

Następne kroki: - Rozwiązuj problemy na platformach: LeetCode, Codeforces, HackerRank - Studiuj zaawansowane techniki: Divide and Conquer DP, DP na drzewach - Stosuj DP w projektach praktycznych

Powodzenia w dalszej nauce algorytmów! 🚀