Znajdowanie w ciągu podciągów o różnorodnych własnościach

W analizie algorytmicznej często spotykamy się z problemami dotyczącymi wyszukiwania fragmentów ciągów (tablic, list) spełniających określone warunki. Takie fragmenty nazywamy podciągami spójnymi (ang. subarrays). W tym rozdziale poznasz najważniejsze typy takich podciągów oraz algorytmy, które pozwalają je znaleźć w czasie liniowym lub bliskim liniowemu.

Podstawowe pojęcia

Ciąg

Ciąg to uporządkowany zbiór elementów, np.:

$A=[a_1,a_2,a_3,\dots ,a_n]$

1. Podciąg spójny

Podciąg spójny to fragment ciągu zawierający kolejne elementy:

$[a_i,a_{i+1},\dots ,a_j]$

Przykład:

Dla ciągu $[3,1,4,1,5]$ podciągami spójnymi są m.in.:

• $[3]$

• $[1,4]$

• $[4,1,5]$

ale nie jest nim $[3,4,5]$, bo elementy nie są sąsiadujące.

2. Najdłuższy spójny podciąg niemalejący

Definicja

Podciąg niemalejący to taki, w którym każdy kolejny element jest nie mniejszy od poprzedniego:

$a_k\le a_{k+1}$

Przykład

Dla ciągu:

$[2,2,3,1,4,4,5]$

najdłuższy podciąg niemalejący to:

$[1,4,4,5]$

Algorytm (czas $O(n)$)

1. Ustaw długość bieżącego podciągu na 1.

2. Przechodź po elementach ciągu.

3. Jeśli $a[i]\le a[i+1]$, wydłuż bieżący podciąg.

4. W przeciwnym razie zacznij nowy.

5. Zapamiętuj maksymalną długość.

3. Spójny podciąg o największej sumie

Dany jest ciąg liczb (mogą być ujemne). Szukamy podciągu spójnego o maksymalnej sumie elementów.

Dla ciągu:

$[-2,3,-1,4,-5,2]$

podciąg o największej sumie to:

$[3,-1,4]$

bo jego suma wynosi $6$.

4. Przykłady krok po kroku

Najdłuższy podciąg niemalejący

Ciąg: [1,2,2,1,3,4,3]

Przebieg:

Wynik: 3

Nie rozwiązuj jeszcze zadania - spróbuj najpierw zastanowić się, jak można to zadanie rozbić na mniejsze kroki, które da się zapamiętać i wykorzystać ponownie. To właśnie pierwszy ruch w stronę programowania dynamicznego.

Szukamy najdłuższego spójnego fragmentu, w którym każda kolejna wartość jest ≥ poprzedniej.

Przejdźmy przez nasz ciąg:

• 2 → 3 rośnie [2,3] (długość 2)

• 3 → -1  spadek // reset - szukamy kolejnego fragmentu

• -1 → 4 → 4  nie maleje [-1,4,4] (długość 3)

• 4 → -2  spadek // reset

• -2 → 5 → 5 → 5 nie maleje [-2,5,5,5] (długość 4)

• 5 → -3 spadek // reset

• -3 → 1 rośnie [-3,1]

Najdłuższy spójny niemalejący podciąg to:

[-2,5,5,5]

Długość: 4

Szukamy najdłuższego spójnego fragmentu, w którym każda kolejna liczba jest nie mniejsza od poprzedniej (czyli ciąg niemalejący).

Krok 1: Ustal, czego szukamy

• Warunek: dla każdej sąsiedniej pary liczb $(a_i,a_{i+1})$ ma być

$a_{i+1}\ge a_i$

• Spójny fragment: wybieramy kolejne elementy z tablicy

Chcemy znaleźć najdłuższy taki fragment.

Krok 2: Przejdź po tablicy od lewej do prawej

Będziemy „budować” aktualny fragment niemalejący i zapamiętywać najdłuższy dotąd znaleziony.

Zaczynamy od pierwszego elementu:

• Aktualny fragment: [2]

• Najlepszy dotąd: [2]

Krok 3: Sprawdzaj kolejne pary

Para: 2 → 3

• Czy $3\ge 2$? Tak 

• Możemy przedłużyć fragment.

Aktualny fragment: [2,3] Najlepszy dotąd: [2,3] (długość 2)

Para: 3 → -1

• Czy $-1\ge 3$? Nie

• Warunek nie jest spełniony → kończymy fragment.

Porównujemy długości:

• dotychczasowy najlepszy: [2,3](długość 2)

• aktualny (też 2) → remis, nic nie zmieniamy.

Zaczynamy nowy fragment od -1:

Aktualny fragment: [-1] Najlepszy dotąd: [2,3]

Para: -1 → 4

• Czy $4\ge -1$? Tak

Aktualny fragment: [-1,4] Najlepszy dotąd: [2,3] (długość 2)

Para: 4 → 4

• Czy $4\ge 4$? Tak 

Aktualny fragment: [-1,4,4] Długość aktualnego: 3 → lepszy niż [2, 3] (długość 2).

Najlepszy dotąd: [-1,4,4] (długość 3)

Para: 4 → -2

• Czy $-2\ge 4$? Nie

Koniec fragmentu [-1,4,4]. Porównujemy długości:

• najlepszy: [-1,4,4] (długość 3)

• aktualny: [-1,4,4] (długość 3) → bez zmian.

Zaczynamy nowy fragment od -2:

Aktualny fragment: [-2] Najlepszy dotąd: [-1,4,4]

Para: -2 → 5

• Czy $5\ge -2$? Tak

Aktualny fragment: [-2,5]

Para: 5 → 5

• Czy $5\ge 5$? Tak

Aktualny fragment: [-2,5,5]

Para: 5 → 5 (druga)

• Czy $5\ge 5$? Tak

Aktualny fragment: [-2,5,5,5] Długość: 4 → lepszy niż dotychczasowy najlepszy (długość 3).

Najlepszy dotąd: [-2,5,5,5] (długość 4)

Para: 5 → -3

• Czy $-3\ge 5$? Nie

Koniec fragmentu [-2,5,5,5].

Porównujemy:

• najlepszy: [-2,5,5,5] (długość4)

• aktualny: [-2,5,5,5] (długość4) → bez zmian.

Zaczynamy nowy fragment od -3:

Aktualny fragment: [-3] Najlepszy dotąd: [-2,5,5,5]

Para: -3 → 1

• Czy $1\ge -3$? Tak

Aktualny fragment: [-3,1] (długość 2) To krótsze niż najlepszy (długość 4), więc nie zmieniamy najlepszego.

Krok 4: Podsumowanie

Po przejściu całej tablicy:

• Najdłuższy spójny niemalejący fragment:

[-2,5,5,5]

• Długość: 4

To jest odpowiedź.

Pseudokod (DP) - najdłuższy spójny podciąg niemalejący

Założenie: Dany jest ciąg A[0..n‑1]. Chcemy znaleźć najdłuższy spójny fragment, w którym

$A[i]\le A[i+1]$

Wejście: tablica liczb A[0..n‑1]

Wyjście: początek i koniec najdłuższego niemalejącego podciągu spójnego

Utwórz tablicę DP[0..n‑1]

DP[0] <-- 1          // każdy element sam w sobie tworzy fragment długości 1
najlepsza_dlugosc <-- 1
najlepszy_koniec <-- 0
Dla i od 1 do n‑1:
    Jeżeli A[i] ≥ A[i‑1]:
        DP[i] <-- DP[i‑1] + 1
    Inaczej:
        DP[i] <-- 1
	Jeśli DP[i] > najlepsza_dlugosc:
		najlepsza_dlugosc <-- DP[i]
		najlepszy_koniec <-- i
najlepszy_poczatek <-- najlepszy_koniec - najlepsza_dlugosc + 1
Zwróć (najlepszy_poczatek, najlepszy_koniec)

Co robi DP w tym algorytmie?

• DP[i] oznacza długość najdłuższego niemalejącego spójnego fragmentu kończącego się na pozycji i.

• Jeśli A[i] ≥ A[i‑1], to możemy „przedłużyć” poprzedni fragment.

• Jeśli nie - zaczynamy nowy fragment od i.

• Najlepszy wynik aktualizujemy na bieżąco, w każdej iteracji pętli.

• Po zakończeniu pętli obliczamy początek fragmentu na podstawie długości i końca.

To klasyczny wzorzec DP: DP[i] zależy tylko od DP[i−1], więc obliczenia są liniowe.

Wynik dla naszego przykładu

Dla tablicy:

[2,3,-1,4,4,-2,5,5,5,-3,1]

algorytm zwróci:

początek = 5

koniec = 8

czyli fragment:

[-2,5,5,5]