Podciągi o własnościach

🎯 Po co Ci to?

Analityk patrzy na dzienne zyski i straty sklepu: [3, -5, 6, 2, -1, 4, -8, 2] — i pyta: który spójny okres był najlepszy? Trener patrzy na wyniki zawodniczki i pyta: jak długo trwała najdłuższa passa poprawy? Oba pytania dotyczą podciągów o zadanej własności — i oba mają rozwiązania tak eleganckie, że aż podejrzane: jedno przejście, jedna-dwie zmienne pomocnicze. Podstawa rozszerzona wymienia oba problemy wprost, a na maturze to stali bywalcy. Po tej jednostce będziesz je łuskać z dowolnej historyjki.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • znaleźć spójny podciąg o największej sumie jednym przejściem (algorytm Kadane'a);
  • znaleźć najdłuższy spójny podciąg niemalejący;
  • rozpoznać wspólny wzorzec: „ciągnę bieżącą serię albo zaczynam nową".

🔁 Przypomnij sobie

Z 8.4: podsłowo/fragment spójny vs podciąg z pominięciami — dziś pracujemy na spójnych; z 3.3: wzorce sumy i licznika w pętli.

📘 Wyjaśnienie

Największa suma spójnego fragmentu. Podejście siłowe: sprawdź wszystkie fragmenty — jest ich ~$n^2/2$, a z sumowaniem każdego koszt rośnie do $n^3$ (dla stu tysięcy dni — wieczność). A wystarczy jedno przejście i jedno pytanie zadawane przy każdym elemencie: czy opłaca się ciągnąć dotychczasowy fragment, czy lepiej zacząć od zera tutaj?

def najlepszy_okres(L):
    biezaca = najlepsza = L[0]
    for x in L[1:]:
        biezaca = max(x, biezaca + x)      # ciągnę serię albo zaczynam nową od x
        najlepsza = max(najlepsza, biezaca)
    return najlepsza

Sedno linijki max(x, biezaca + x): jeśli dotychczasowa suma biezaca jest ujemna, to doklejanie jej do $x$ tylko szkodzi — lepiej zacząć świeży fragment od $x$. Jeśli dodatnia — ciągniemy. Dla danych sklepu: 3, -2, 6, 8, 7, 11, 3, 5 (wartości biezaca) — maksimum 11 (okres 6, 2, -1, 4). Ten algorytm nosi nazwisko Kadane'a i jest ulubionym przykładem na to, że dynamiczne programowanie nie zawsze potrzebuje tabeli: podproblem „najlepszy fragment kończący się tutaj" ma zależność sięgającą tylko o jeden wstecz, więc wystarczy zmienna. (Rozpoznajesz? To „okno" z Fibonacciego 4.3 — tabela zredukowana do tego, co naprawdę potrzebne.)

Najdłuższa passa niemalejąca. Ta sama melodia, inny refren: idź po liście, licz długość bieżącej serii niemalejącej; gdy element spada względem poprzedniego — seria się zrywa, licznik wraca do 1:

def najdluzsza_passa(L):
    biezaca = najlepsza = 1
    for i in range(1, len(L)):
        if L[i] >= L[i - 1]:
            biezaca = biezaca + 1          # seria trwa
        else:
            biezaca = 1                    # zerwanie: nowa seria od tego elementu
        najlepsza = max(najlepsza, biezaca)
    return najlepsza

Dla [2, 2, 5, 3, 4, 7, 7, 1]: serie 2,2,5 (3) → zerwanie → 3,4,7,7 (4) → zerwanie → 1. Wynik: 4. Jedno przejście, dwie zmienne — koszt $O(n)$ tam, gdzie siłowe podejście kwadratowe.

💭 Pomyśl: Oba algorytmy mają identyczny szkielet: biezaca (najlepsze coś kończące się tutaj) i najlepsza (najlepsze gdziekolwiek). Czemu potrzebne są obie zmienne? Znajdź dane, na których pomylenie ich (zwrócenie biezaca) daje zły wynik.

Sprawdź odpowiedź

Najlepszy fragment rzadko kończy się na ostatnim elemencie! Dla zysków [5, 6, -100]: biezaca na końcu to $-89$, ale najlepsza zapamiętała 11 z wcześniej. Zwrócisz biezaca — zgłosisz katastrofę zamiast świetnego okresu. Rozdział ról: biezaca to sonda lokalna (musi umieć spadać), najlepsza — kronikarz rekordu (nigdy nie spada). Ten duet „sonda + kronikarz" to wzorzec wart zapamiętania na zawsze; zobaczysz go w dziesiątkach zadań, od pogody po giełdę.

⚠️ Uwaga, pułapka

Brzegi tych zadań gryzą w dwóch miejscach. Lista samych ujemnych [-3, -1, -7]: poprawna odpowiedź na „największa suma fragmentu" to $-1$ (najmniej zły jednoelementowy) — inicjalizacja najlepsza = 0 (częsty odruch!) skłamie, że najlepszy okres ma sumę 0, czyli… fragment pusty, którego zadanie zwykle nie dopuszcza. Dlatego startujemy z L[0], nie z zera. Niemalejący ≠ rosnący: >= dopuszcza równość (passa 7, 7 trwa); zadanie o serii rosnącej wymaga > — jedna kreska, inny wynik. Czytaj treść jak prawnik (to już trzeci raz w tym dziale — bo w optymalizacji drobiazgi sformułowania rządzą wszystkim).

🛠️ Teraz Ty

Bez komputera: dla temperatury [12, 15, 15, 11, 13, 18, 21, 2, 8] znajdź najdłuższą passę niemalejącą (ręcznie, z tabelką biezaca/najlepsza). Z komputerem: rozszerz najlepszy_okres tak, by zwracał też indeksy początku i końca najlepszego fragmentu (podpowiedź: zapamiętuj początek bieżącej serii przy każdym „zaczynam nową"). Przetestuj na danych sklepu i na samych ujemnych.

📐 Definicje tej lekcji

  • Algorytm Kadane'a — największa suma spójnego fragmentu: biezaca = max(x, biezaca + x), kronikarz najlepsza; $O(n)$.
  • Wzorzec sonda + kronikarz — „najlepsze kończące się tutaj" + „najlepsze dotąd"; obsługuje sumy, passy, serie.

📌 Najważniejsze w pigułce

  • Kluczowe pytanie przy każdym elemencie: ciągnąć serię czy zacząć nową? — ujemna suma/zerwanie porządku = zacznij nową.
  • Dwie zmienne zamiast tabeli, bo zależność sięga tylko o jeden wstecz — dynamiczne w wersji kieszonkowej.
  • Brzegi: same ujemne (start z L[0], nie 0) i >= kontra > (niemalejący vs rosnący).

🎒 Zadania

  1. Przejdź algorytmem Kadane'a listę [4, -1, -1, 5, -9, 6], notując obie zmienne. Jaki fragment wygrał?
Wskazówka i odpowiedź

biezaca: 4, 3, 2, 7, -2, 6; najlepsza: 4, 4, 4, 7, 7, 7. Wygrał fragment [4, -1, -1, 5] z sumą 7 — zauważ, że algorytm „przełknął" dwie małe straty, bo seria wciąż była na plusie, ale po $-9$ (suma $-2$) opłaciło się zacząć od nowa. Dokładnie tak analityk czyta „słabszy tydzień w dobrym kwartale" kontra „załamanie".

  1. Zaprojektuj wariant: najdłuższa passa, w której elementy są na przemian rosnące i malejące (zygzak: 3, 7, 2, 5, 1…). Co jest „zerwaniem" i czego musi pamiętać sonda?
Wskazówka i odpowiedź

Zerwanie: dwa kolejne ruchy w tę samą stronę (albo równość). Sonda musi pamiętać długość bieżącego zygzaka i kierunek ostatniego ruchu (w górę/w dół) — nowy element przedłuża serię tylko, gdy rusza w przeciwną stronę niż poprzednio. Szkielet ten sam: przedłuż albo zacznij nową (długości 2, od poprzedniego elementu). Wzorzec z 📘 przyjmuje dowolną definicję „serii" — wystarczy umieć powiedzieć, co ją podtrzymuje, a co zrywa.

  1. Giełdowy klasyk: mając ceny akcji dzień po dniu [7, 1, 5, 3, 6, 4], znajdź najlepszy zysk z jednej transakcji (kup raz, sprzedaj później). Pokaż, że to problem z tej jednostki w przebraniu.
Wskazówka i odpowiedź

Zysk transakcji = suma dziennych zmian cen między kupnem a sprzedażą (zmiany: $-6, 4, -2, 3, -2$). Najlepsza transakcja = spójny fragment zmian o największej sumie = Kadane! Fragment 4, -2, 3 daje 5: kup za 1 (dzień 2), sprzedaj za 6 (dzień 5). Przebranie zdjęte jednym spostrzeżeniem „zysk to suma zmian" — i to jest właśnie redukcja z 1.6: sprowadź nowy problem do rozwiązanego. Trzy działy podały sobie ręce w jednym zadaniu.

🔍 Sprawdź, czy umiesz

  • Wykonać Kadane'a i passę ręcznie, prowadząc sondę i kronikarza.
  • Uzasadnić inicjalizację L[0] i różnicę >=/>.
  • Rozpoznać wzorzec serii w nowej historyjce (zygzak, giełda, pogoda).

Ucz się tej jednostki z asystentem