Czego się nauczysz
Nauczysz się znajdować w jednym przejściu przez dane najdłuższy fragment niemalejący i fragment o największej sumie. Na maturze to np. najdłuższy okres kolejnych cieplejszych dni albo najlepsza seria wyników.
Po co ci to na maturze
Najdłuższa seria coraz cieplejszych dni, najdłuższy ciąg rosnących pomiarów, najlepsza passa wyników: takie pytania to klasyka zadań z plikiem. Odpowiedź da się znaleźć w jednym przejściu przez dane.
Etapy lekcji
Spis lekcji
Teoria
6 rozdziałówNie zaczęte- 1.1Fragment spójnyKolejne elementy bez przerw, jak kawałek taśmy wycięty nożyczkami.
- 1.2Najdłuższy fragment niemalejącyDługość bieżącego fragmentu rośnie albo wraca do 1, a rekord sprawdzasz w każdym obrocie.
- 1.3Gdzie zaczyna się rekord i co z remisemZapamiętaj początek bieżącego fragmentu, a rekord zmieniaj tylko przy ściśle większej długości.
- 1.4Fragment o największej sumieGdy dotychczasowa suma jest ujemna, opłaca się zacząć od nowa: algorytm Kadanego.
- 1.5Dlaczego nie wszystkie fragmentyCiąg 1000 liczb ma ponad pół miliona fragmentów. Jedno przejście wystarcza.
- 1.6PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.