C++ · Etap 2 · Lekcja 13

Max i min — największy, najmniejszy, najlepszy

„Jaka jest najwyższa temperatura?”, „Kto zdobył najwięcej punktów?”, „Ile najmniej trzeba zapłacić?” — prawie każde zadanie pyta o coś naj. W tej lekcji poznasz wszystkie narzędzia do takich pytań: funkcje max i min dla dwóch, trzech i wielu liczb, rekord w pętli, szukanie miejsca rekordu, gotowce max_element i min_element, przycinanie wyniku do dozwolonych granic, dwie największe liczby w jednym przejściu, rekordy liczone na bieżąco i klasyczne pomysły: najlepszy zysk, najdłuższa seria i największa suma fragmentu. Najważniejsze schematy obejrzysz w animacjach krok po kroku, a po każdej części czekają ćwiczenia ze sprawdzarką.

68 ćwiczeń w trakcie lekcji28 zadań w bazie na koniec96 ze sprawdzarką C++

Co już umiesz i czego się nauczysz

Ta lekcja zakłada, że przerobiłeś wszystkie poprzednie: Typy zmiennych, Input / Output, If / Else, While loop, For loop, Modulo, Tablice, String, Pair, Vector i Sortowanie. Niczego nowego o samym języku nie trzeba tu znać — wystarczą pętle, if, tablice i vector.

Z funkcjami max i min już się mijałeś: pojawiły się na chwilę w lekcji o instrukcji if, przy przedziałach w lekcji o parach, a w lekcji o vectorze poznałeś strzałkę max_element. Za każdym razem były jednak tylko dodatkiem. Teraz dostają własną lekcję, bo szukanie największej i najmniejszej wartości to jedna z najczęstszych rzeczy w programowaniu — i pełno w niej pułapek: od czego zacząć rekord? Co, gdy wszystkie liczby są ujemne? Co, gdy rekord się powtarza? Dlaczego max(3, 2.5) się nie kompiluje? Jak znaleźć drugą największą liczbę?

Uczymy się tak samo jak poprzednio. Przepisuj przykłady do swojego edytora i uruchamiaj je. Przy pytaniach „Co wypisze program?” najpierw zapisz sobie na kartce zmienne (na przykład maks i mini) i śledź program linijka po linijce, a dopiero potem sprawdzaj odpowiedź. Animacje możesz klikać krok po kroku — spróbuj za każdym razem przewidzieć, co stanie się po kliknięciu. Po każdej części rób ćwiczenia w sprawdzarce. Lekcja jest długa: rób przerwy i nie przechodź dalej, dopóki ćwiczenia z poprzedniej części nie przestaną sprawiać Ci kłopotu.

CZĘŚĆ 01–02

Kilka liczb

max(a, b) i min(a, b) od podstaw, pułapka różnych typów, trzy liczby, lista w klamrach i liczba środkowa.

CZĘŚĆ 03–05

Rekord w danych

Rekord w pętli i wartość startowa, pozycja rekordu i remisy, a potem gotowce max_element i min_element.

CZĘŚĆ 06–07

Granice i dwie najlepsze

„Nie mniej niż zero, nie więcej niż limit”, wspólna część przedziałów, dwie największe liczby i najlepsza para.

CZĘŚĆ 08–09

Max i min w akcji

Rekordy liczone na bieżąco, najlepszy zysk, najdłuższa seria, najlepsze okno, największa suma fragmentu i tabele.

Przypomnienie: złota zasada sprawdzarki Sprawdzarka porównuje Twoje wyjście z oczekiwanym znak po znaku, więc wypisujesz dokładnie to, o co prosi zadanie — bez „Podaj liczby:” i bez dodatkowych słów. Spacje na końcu wiersza są ignorowane, więc wypisywanie liczb pętlą z cout << x << " " jest w porządku. W tej lekcji szczególnie uważaj na ograniczenia w treści zadania: to one mówią, czy liczby mogą być ujemne i czy wynik zmieści się w int, czy potrzebny będzie long long.

Mapa lekcji

max i min — większa i mniejsza z dwóch

Zaczynamy od najprostszej sytuacji: masz dwie liczby i chcesz wiedzieć, która jest większa. Umiesz to już zrobić instrukcją if, ale C++ ma na to dwie gotowe funkcje, które będziesz pisać tysiące razy: max i min. W tej części zobaczysz, jak działają, co dokładnie „oddają”, jak zachowują się dla liczb ujemnych, liter i napisów, oraz poznasz jedyną pułapkę, na którą trzeba uważać — typy.

Pierwszy program

max(a, b) to większa z liczb a i b, a min(a, b) to mniejsza. Nazwy pochodzą od łacińskich słów maximum (największy) i minimum (najmniejszy). Obie funkcje mieszkają w bibliotece <algorithm>, ale <bits/stdc++.h> ma ją w środku, więc niczego nie dopisujesz.

pierwszy.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << max(a, b) << "\n";   // większa
    cout << min(a, b) << "\n";   // mniejsza
    return 0;
}
▶ Wejście 1
7 3
▶ Wyjście 1
7 3
▶ Wejście 2
-4 -9
▶ Wyjście 2
-4 -9
▶ Wejście 3
5 5
▶ Wyjście 3
5 5

Ten sam program uruchomiliśmy trzy razy, z różnymi danymi.

Za pierwszym razem wszystko jest oczywiste: 7 jest większe od 3.

Za drugim razem liczby są ujemne. Która jest większa: −4 czy −9? Większa jest ta, która leży bardziej na prawo na osi liczbowej, czyli bliżej zera: −4. Program to wie — nie musisz się o to martwić.

Za trzecim razem liczby są równe. Wtedy i większa, i mniejsza to po prostu 5. Nie ma tu żadnego błędu ani wyjątku.

zapiswynikdlaczego
max(3, 8)88 jest większe od 3
min(3, 8)33 jest mniejsze od 8
max(-3, -8)−3−3 leży bliżej zera, bardziej na prawo na osi
min(-3, -8)−8−8 leży dalej na lewo
max(0, -5)0każda liczba ujemna jest mniejsza od zera
min(6, 6)6gdy liczby są równe, wynik jest taki sam

max oddaje wartość — możesz jej użyć, jak chcesz

Pomyśl o max(a, b) jak o działaniu, tak jak o a + b. Komputer je wylicza i w tym miejscu programu pojawia się wynik. Taki wynik możesz wypisać, zapisać do zmiennej, pomnożyć, dodać do czegoś albo porównać — wszystko, co robisz ze zwykłą liczbą.

wartosc.cpp
int a = 12, b = 30;
int w = max(a, b);                       // w = 30
cout << w << "\n";
cout << max(a, b) * 2 << "\n";           // 30 * 2
cout << max(a, b) - min(a, b) << "\n";   // 30 - 12
cout << max(a, 20) << "\n";              // a z liczbą
cout << a << " " << b << "\n";           // a i b bez zmian
▶ Wyjście
30 60 18 20 12 30

Zwróć uwagę na trzy rzeczy.

Argumentami nie muszą być zmienne — max(a, 20) porównuje zmienną z liczbą.

max(a, b) - min(a, b) to odległość między liczbami: od większej odejmujemy mniejszą, więc wynik nigdy nie jest ujemny. To dokładnie to samo co abs(a - b).

Ostatni wiersz: max i min niczego nie zmieniają. Tylko patrzą na a i b i oddają wynik. Zmienne mają te same wartości co na początku.

Wynik, którego nikt nie zapisał, przepada Częsty błąd początkujących: max(a, b); w osobnej linijce, a potem cout << a; w nadziei, że w a jest teraz większa liczba. Nie jest! Funkcja policzyła wynik, ale nikt go nie zapisał ani nie wypisał, więc przepadł. Jeśli chcesz, żeby a stało się większą z dwóch liczb, napisz a = max(a, b);. Kompilator z włączonymi ostrzeżeniami (-Wall) nawet o tym przypomni: warning: ignoring return value of max — „ignorujesz wynik funkcji max”.
przepada.cpp
int a = 4, b = 9;
max(a, b);           // wynik nikomu się nie przydał
cout << a << "\n";
a = max(a, b);       // teraz zapisujemy go do a
cout << a << "\n";
▶ Wyjście
4 9

Zapis a = max(a, b); czytaj tak: „nowe a to większa z liczb: stare a i b”. Jeśli b było większe, a dostaje wartość b. Jeśli nie — a zostaje takie, jakie było.

Ten zapis będzie bohaterem części 3: w pętli zamieni się w maks = max(maks, x); — rekord, który poprawia się z każdą wczytaną liczbą.

To samo bez max — dla porównania

Żeby nie było w tym magii: max robi dokładnie to, co umiesz już napisać instrukcją if. Poniżej trzy sposoby na tę samą rzecz. Wszystkie dają ten sam wynik — ale wersja z max mieści się w jednej krótkiej linijce i trudniej się w niej pomylić.

trzy_sposoby.cpp
int a = 8, b = 13;

int w1;                       // sposób 1: if / else
if (a > b) w1 = a;
else w1 = b;

int w2 = (a > b ? a : b);     // sposób 2: ?: z lekcji o if
int w3 = max(a, b);           // sposób 3: max

cout << w1 << " " << w2 << " " << w3 << "\n";
▶ Wyjście
13 13 13

Kiedy więc wybrać if, a kiedy max? Gdy chcesz tylko poznać większą liczbę — max. Gdy przy okazji musisz zrobić coś więcej (zapamiętać, kto miał więcej punktów, albo wypisać komunikat) — if. Do tej drugiej sytuacji wrócimy w części 4.

Najważniejsza pułapka: oba argumenty tego samego typu

max i min mają jeden kaprys: oba argumenty muszą być dokładnie tego samego typu. Dwa int-y — dobrze. Dwa double — dobrze. Ale int i double naraz — błąd kompilacji, i to z długim, strasznym komunikatem, w którym zobaczysz coś w rodzaju no matching function for call to max(int, double) oraz deduced conflicting types. Kompilator nie wie, jakiego typu ma być wynik, więc się poddaje.

zle_typy.cpp
cout << max(3, 2.5) << "\n";   // int i double — błąd
▶ Kompilator
error: no matching function for call to 'max(int, double)'
dobre_typy.cpp
cout << max(3.0, 2.5) << "\n";      // dwa double
int a = 3;
double b = 2.5;
cout << max((double)a, b) << "\n";  // a zamienione na double
cout << max(1.5, 2.25) << "\n";
▶ Wyjście
3 3 2.25

Liczba 3 to dla C++ int, a 3.0 to double. Gdy porównujesz zmienną typu int ze zmienną typu double, zamień jedną z nich przed porównaniem: (double)a to wartość a jako double — tak samo jak w lekcji o typach zmiennych.

Najczęściej ta pułapka łapie przy long long. Liczba 7 napisana w programie to int, więc max(x, 7) dla long long x się nie skompiluje. Dopisz na końcu liczby literki LL — wtedy 7LL jest typu long long — albo zamień ją: (long long)7.

long_long_zle.cpp
long long x = 5000000000LL;
cout << max(x, 7) << "\n";    // long long i int — błąd
▶ Kompilator
error: no matching function for call to 'max(long long int&, int)'
long_long_dobrze.cpp
long long x = 5000000000LL;   // 5 miliardów — nie mieści się w int
cout << max(x, 7LL) << "\n";
cout << min(x, (long long)7) << "\n";
▶ Wyjście
5000000000 7
Zasada jednego typu max(int, int) ✓ · max(double, double) ✓ · max(long long, long long) ✓ · max(int, double) ✗ · max(long long, int) ✗. Gdy kompilator krzyczy „no matching function for call to max”, prawie zawsze chodzi o to, że argumenty mają różne typy. Poprawka: 3.0 zamiast 3, 7LL zamiast 7 albo zamiana typu w nawiasie, np. (double)a.

Nie tylko liczby: znaki i napisy

max i min działają dla wszystkiego, co da się porównać znakiem <. Znaki porównują się po kodach (pamiętasz z lekcji o napisach: wielkie litery 65–90, małe 97–122), a napisy — w porządku słownikowym, litera po literze. Pary z lekcji o parach też: najpierw po first, a przy remisie po second.

znaki_napisy.cpp
cout << max('k', 'c') << "\n";
cout << min('Z', 'a') << "\n";      // 'Z' ma kod 90, 'a' — 97
string s = "kot", t = "kotek";
cout << max(s, t) << "\n";
cout << min(s, t) << "\n";
pair<int, int> p = {2, 9}, q = {2, 5};
cout << max(p, q).second << "\n";   // remis na first, wygrywa second
▶ Wyjście
k Z kotek kot 9

max('k', 'c') to litera, która jest dalej w alfabecie.

min('Z', 'a') to wielkie Z, bo wszystkie wielkie litery mają mniejsze kody od małych — tak samo jak przy sortowaniu.

Napis „kot” jest początkiem napisu „kotek”, więc w słowniku stoi wcześniej — jest „mniejszy”.

Pary (2, 9) i (2, 5) remisują na first, więc rozstrzyga second: większa jest (2, 9).

Dwa przykłady z życia

W prawdziwych zadaniach max i min rzadko pojawiają się „gołe”. Zwykle w treści jest słowo: lepszy, tańszy, dłuższy, wcześniejszy. Twoim zadaniem jest przetłumaczyć je na max albo min.

skoki.cpp
// Zawodnik oddaje dwa skoki, liczy się lepszy.
double s1, s2;
cin >> s1 >> s2;
cout << "Wynik: " << max(s1, s2) << "\n";
▶ Wejście
6.45 6.8
▶ Wyjście
Wynik: 6.8
sklepy.cpp
// Ta sama rzecz w dwóch sklepach — kupujemy taniej.
int sklepA, sklepB;
cin >> sklepA >> sklepB;
cout << "Zaplacisz: " << min(sklepA, sklepB) << "\n";
cout << "Oszczedzisz: " << max(sklepA, sklepB) - min(sklepA, sklepB) << "\n";
▶ Wejście
129 99
▶ Wyjście
Zaplacisz: 99 Oszczedzisz: 30
Słownik: z treści zadania na kod większy, lepszy, dłuższy, wyższy, późniejszy, „co najmniej”, „nie mniej niż” → najczęściej max · mniejszy, tańszy, krótszy, niższy, wcześniejszy, „co najwyżej”, „nie więcej niż” → najczęściej min. Uwaga na czas: „najlepszy czas biegu” to najkrótszy, czyli min!
Sprawdź się w głowie

Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
cout << max(4, 9) << min(4, 9);
Pokaż odpowiedź
94Najpierw większa (9), potem mniejsza (4) — bez spacji, bo jej nie wypisujemy.
Co wypisze ten fragment?
cout << max(-2, -7);
Pokaż odpowiedź
-2−2 leży bliżej zera, więc jest większa od −7.
Co wypisze ten fragment?
int a = 5;
max(a, 10);
cout << a;
Pokaż odpowiedź
5Wynik max nie został nigdzie zapisany, więc przepadł. a się nie zmieniło.
Co wypisze ten fragment?
int a = 5;
a = max(a, 10);
a = min(a, 7);
cout << a;
Pokaż odpowiedź
7Najpierw a = max(5, 10) = 10, potem a = min(10, 7) = 7.
Co wypisze ten fragment?
cout << max('a', 'B');
Pokaż odpowiedź
aMałe 'a' ma kod 97, a wielkie 'B' — 66. Większy kod wygrywa.
Co wypisze ten fragment?
cout << min(7, 7) + max(3, 3);
Pokaż odpowiedź
10Przy równych liczbach wynikiem jest ta sama liczba: 7 + 3 = 10.
Co wypisze ten fragment?
int a = 3, b = 8;
cout << max(a, b) - min(a, b) << " ";
cout << min(a, b) - max(a, b);
Pokaż odpowiedź
5 -5Większa minus mniejsza to odległość (zawsze ≥ 0). Odwrotnie wychodzi liczba przeciwna.
Co wypisze ten fragment?
string x = "ala", y = "Ola";
cout << max(x, y);
Pokaż odpowiedź
alaPorównujemy pierwsze litery: 'a' (97) i 'O' (79). Małe litery mają większe kody, więc „ala” jest „większe”.
Co wypisze ten fragment?
cout << max(2.5, 2.25) * 2;
Pokaż odpowiedź
5max(2.5, 2.25) = 2.5, a 2.5 · 2 = 5 (double 5.0 wypisuje się jako 5).
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Trzy, cztery, pięć liczb — max w max i lista w klamrach

max(a, b) porównuje dokładnie dwie liczby. A co, gdy liczb jest trzy albo pięć? Są dwa sposoby: wkładać jedno max w drugie albo podać wszystkie liczby naraz w klamrach. Poznasz oba, a potem użyjesz ich do trzech klasycznych zadań: noty sędziów, liczba środkowa i trójkąt.

max w max — czytamy od środka

Największą z trzech liczb dostaniesz tak: max(a, max(b, c)). Komputer liczy to od środka, tak jak nawiasy w matematyce: najpierw max(b, c) — większa z b i c — a potem porównuje ten wynik z a. To jak turniej: najpierw grają b i c, a zwycięzca gra w finale z a.

trzy.cpp
int a = 4, b = 9, c = 6;
cout << max(a, max(b, c)) << "\n";
cout << min(a, min(b, c)) << "\n";
cout << max(max(a, b), c) << "\n";   // inna kolejność, ten sam wynik
▶ Wyjście
9 4 9
krokco liczymywynik
1max(b, c) = max(9, 6)9
2max(a, 9) = max(4, 9)9

Kolejność „meczów” nie ma znaczenia: największa liczba wygra każdy mecz, w którym zagra, więc zawsze dojdzie do końca.

Dla czterech liczb wkładamy jeszcze głębiej: max(max(a, b), max(c, d)) — dwa półfinały i finał. Działa, ale przy pięciu liczbach nawiasów robi się tyle, że łatwo się w nich zgubić. Dlatego jest drugi sposób.

Lista w klamrach: max({…})

Wszystkie liczby możesz podać naraz, w klamrach wewnątrz nawiasów: max({a, b, c, d, e}). Klamry tworzą listę — taką samą, jakiej używałeś do wypełniania vectora: vector<int> v = {4, 9, 6};. Liczb w liście może być dowolnie wiele.

klamry.cpp
int a = 4, b = 9, c = 6, d = -2, e = 9;
cout << max({a, b, c, d, e}) << "\n";
cout << min({a, b, c, d, e}) << "\n";
cout << max({3, 1, 4, 1, 5, 9, 2, 6}) << "\n";
long long x = 7000000000LL;
cout << max({x, 5LL, 0LL}) << "\n";   // wszystkie long long
▶ Wyjście
9 -2 9 7000000000

Zasada jednego typu z części 1 obowiązuje także tutaj: wszystkie elementy listy muszą mieć ten sam typ. Dlatego przy long long x piszemy 5LL i 0LL.

Uważaj na nawiasy: klamry są w środku okrągłych. max(3, 8, 5) bez klamer to błąd — trzecie miejsce w nawiasie jest zarezerwowane na coś zupełnie innego (regułę porównania, jak w sort), a liczba 5 regułą nie jest.

bez_klamer.cpp
cout << max(3, 8, 5) << "\n";   // brak klamer — błąd
▶ Kompilator
error: '__comp' cannot be used as a function
Dwie liczby czy więcej? Dwie liczby: max(a, b). Trzy i więcej: max({a, b, c}) — klamry w środku nawiasów. Wszystkie elementy tego samego typu.

Noty sędziów: odrzuć najwyższą i najniższą

W skokach narciarskich pięciu sędziów ocenia styl skoczka. Żeby jeden zbyt surowy albo zbyt łaskawy sędzia nie zepsuł wyniku, odrzuca się najwyższą i najniższą notę, a pozostałe trzy się sumuje. W programie to jedna linijka: suma wszystkich minus największa minus najmniejsza.

noty.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    double n1, n2, n3, n4, n5;
    cin >> n1 >> n2 >> n3 >> n4 >> n5;
    double suma = n1 + n2 + n3 + n4 + n5;
    double najw = max({n1, n2, n3, n4, n5});
    double najm = min({n1, n2, n3, n4, n5});
    cout << suma - najw - najm << "\n";
    return 0;
}
▶ Wejście
18.5 19 17.5 18 20
▶ Wyjście
55.5

Suma wszystkich not: 18.5 + 19 + 17.5 + 18 + 20 = 93.

Najwyższa nota to 20, najniższa — 17.5. Odrzucamy je: 93 − 20 − 17.5 = 55.5, czyli suma not 18.5, 19 i 18.

A gdyby dwóch sędziów dało po 20? Odrzucamy tylko jedną z nich — i program robi dokładnie to, bo od sumy odejmuje liczbę 20 tylko raz.

Liczba środkowa i trzy liczby po kolei

Z trzech liczb jedna jest największa, jedna najmniejsza, a trzecia — środkowa. Jak ją znaleźć bez sortowania? Tą samą sztuczką co przy sędziach: od sumy wszystkich trzech odejmij największą i najmniejszą. Zostaje dokładnie ta trzecia. Mając wszystkie trzy, możesz wypisać liczby po kolei.

po_kolei.cpp
int a, b, c;
cin >> a >> b >> c;
int mn = min({a, b, c});
int mx = max({a, b, c});
int sr = a + b + c - mn - mx;
cout << mn << " " << sr << " " << mx << "\n";
▶ Wejście 1
7 2 5
▶ Wyjście 1
2 5 7
▶ Wejście 2
4 9 4
▶ Wyjście 2
4 4 9

Pierwsze dane: suma to 14, największa 7, najmniejsza 2, więc środkowa to 14 − 7 − 2 = 5.

Drugie dane: dwie czwórki. Najmniejsza to 4, największa 9, a środkowa 17 − 9 − 4 = 4 — druga czwórka. Sztuczka działa także przy powtórzeniach.

Uwaga na sumę dużych liczb Jeśli liczby mogą sięgać miliarda, ich suma przekroczy zakres int (około 2,1 miliarda) i wynik wyjdzie bez sensu. W takim zadaniu wczytuj liczby do long long — i pamiętaj, że wtedy wszystkie argumenty max i min też muszą być long long.

Czy z trzech patyków zbudujesz trójkąt?

Masz trzy patyki o długościach a, b i c. Trójkąt da się zbudować wtedy, gdy najdłuższy patyk jest krótszy od dwóch pozostałych razem. Jeśli jest równy ich sumie albo dłuższy, dwa krótsze patyki „nie dosięgną” do siebie. Sprawdzać wszystkie trzy warunki (a < b + c, b < a + c, c < a + b) nie trzeba — wystarczy jeden, dla najdłuższego.

trojkat.cpp
long long a, b, c;
cin >> a >> b >> c;
long long najdl = max({a, b, c});
long long reszta = a + b + c - najdl;   // suma dwóch krótszych
if (najdl < reszta) cout << "TAK\n";
else cout << "NIE\n";
▶ Wejście 1
3 4 5
▶ Wyjście 1
TAK
▶ Wejście 2
1 2 3
▶ Wyjście 2
NIE
▶ Wejście 3
10 3 4
▶ Wyjście 3
NIE

3, 4, 5: najdłuższy ma 5, pozostałe razem 7. 5 < 7 — trójkąt jest.

1, 2, 3: najdłuższy ma 3, pozostałe razem też 3. Patyki ułożyłyby się w płaski odcinek, a nie w trójkąt — NIE.

10, 3, 4: patyki 3 i 4 razem mają 7, a to mniej niż 10 — NIE.

Używamy long long, bo patyki mogą być długie, a ich suma większa od zakresu int.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
cout << max(3, max(8, 5));
Pokaż odpowiedź
8Najpierw max(8, 5) = 8, potem max(3, 8) = 8.
Co wypisze ten fragment?
cout << min(min(4, -1), 2);
Pokaż odpowiedź
-1min(4, −1) = −1, a min(−1, 2) = −1.
Co wypisze ten fragment?
cout << max({3, 9, 4, 9});
Pokaż odpowiedź
9Dwie dziewiątki nie przeszkadzają — wynikiem jest wartość 9.
Co wypisze ten fragment?
int a = 6, b = 1, c = 4;
cout << a + b + c - max({a, b, c}) - min({a, b, c});
Pokaż odpowiedź
411 − 6 − 1 = 4 — liczba środkowa.
Co wypisze ten fragment?
cout << max(min(5, 2), min(3, 7));
Pokaż odpowiedź
3Od środka: min(5, 2) = 2 i min(3, 7) = 3, a max(2, 3) = 3.
Co wypisze ten fragment?
cout << min({7, 3, 5}) * max({1, 2});
Pokaż odpowiedź
6Najmniejsza z listy to 3, największa z drugiej — 2. 3 · 2 = 6.
Co wypisze ten fragment?
long long x = 4;
cout << max({x, 10LL, 2LL});
Pokaż odpowiedź
10Wszystkie elementy listy są typu long long, więc wszystko się kompiluje. Największy jest 10.
Co wypisze ten fragment?
cout << max(max(1, 2), max(3, 4)) - min(min(1, 2), min(3, 4));
Pokaż odpowiedź
3Największa z czterech to 4, najmniejsza to 1. 4 − 1 = 3.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Rekord: maks = max(maks, x)

Lista w klamrach działa, gdy liczb jest kilka i znasz je, pisząc program. Ale w zadaniach liczb jest zwykle n — i n poznajesz dopiero po wczytaniu danych. Może ich być pięć, a może sto tysięcy. Wtedy potrzebny jest rekord: jedna zmienna, która pamięta najlepszą wartość widzianą do tej pory i poprawia się przy każdej kolejnej liczbie. To najważniejszy schemat tej lekcji — rekord pojawi się prawie w każdym zadaniu.

Sędzia na zawodach w skoku w dal

Sędzia nie musi zapisywać wszystkich skoków, żeby po zawodach wiedzieć, który był najdłuższy. Wystarczy, że trzyma w głowie dotychczasowy rekord. Po każdym skoku porównuje: jeśli nowy skok jest dłuższy, rekord się zmienia; jeśli nie — zostaje. Po ostatnim skoku rekord jest wynikiem całych zawodów. W programie „porównaj i weź lepszy” to dokładnie maks = max(maks, x);.

Rekord w pętli — animacja
Animacja działa po włączeniu JavaScriptu.
rekord.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int maks;
    cin >> maks;               // pierwsza liczba = rekord na start
    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;
        maks = max(maks, x);   // lepszy z: stary rekord, x
    }
    cout << maks << "\n";
    return 0;
}
▶ Wejście
8 38 27 43 3 9 82 10 56
▶ Wyjście
82
ixmaks przedmaks po
start——38
1273838
2433843
334343
494343
5824382
6108282
7568282

Pierwszą liczbę wczytujemy przed pętlą i od razu robimy z niej rekord. Dlatego pętla zaczyna się od i = 1 — przechodzi już tylko po pozostałych n − 1 liczbach. Zauważ też, że nie potrzebujemy ani tablicy, ani vectora: każdą liczbę oglądamy raz, porównujemy z rekordem i zapominamy. Program działa tak samo dla 8 liczb i dla miliona.

Od czego zacząć rekord? Pułapka zera

Kusi, żeby zacząć od int maks = 0; i wczytywać wszystkie liczby w pętli. Dla liczb dodatnich to nawet zadziała. Ale zobacz, co się stanie, gdy wszystkie liczby są ujemne:

zero_zle.cpp
int n;
cin >> n;
int maks = 0;                  // ZŁY start!
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    maks = max(maks, x);
}
cout << maks << "\n";
▶ Wejście
4 -7 -2 -15 -3
▶ Wyjście — złe!
0

Żadna z liczb −7, −2, −15, −3 nie jest większa od zera, więc rekord ani razu się nie zmienił i program wypisał 0 — liczbę, której w ogóle nie ma w danych. Poprawna odpowiedź to −2.

To jeden z najczęstszych błędów na zawodach, bo program przechodzi przykład z treści (zwykle z liczbami dodatnimi), a pada dopiero na ukrytym teście z ujemnymi. Z min jest tak samo: start od 0 przy samych dodatnich liczbach daje 0.

Są dwa bezpieczne sposoby. Pierwszy: zacznij od pierwszej liczby z danych — ona na pewno w nich jest. Drugi: zacznij od liczby, która na pewno jest gorsza od każdej możliwej. Dla maksimum to bardzo mała liczba, a dla minimum — bardzo duża. C++ ma na to gotowe stałe z lekcji o typach: INT_MIN (najmniejszy możliwy int, około −2,1 miliarda) i INT_MAX (największy, około 2,1 miliarda). Dla long long są LLONG_MIN i LLONG_MAX.

int_min.cpp
int n;
cin >> n;
int maks = INT_MIN;   // gorszy od każdej liczby
int mini = INT_MAX;   // większy od każdej liczby
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    maks = max(maks, x);
    mini = min(mini, x);
}
cout << maks << " " << mini << "\n";
▶ Wejście
4 -7 -2 -15 -3
▶ Wyjście
-2 -15
Start rekordu — trzy zasady 1) Najpewniej: pierwsza liczba z danych. 2) Albo stała gorsza od wszystkiego: INT_MIN dla maksimum, INT_MAX dla minimum. 3) Nigdy 0, jeśli zadanie nie gwarantuje, że liczby są dodatnie (dla maksimum) albo ujemne (dla minimum). Ograniczenia w treści zadania mówią, jakie liczby mogą się pojawić — zawsze je czytaj.

Największa i najmniejsza w jednej pętli

Nic nie stoi na przeszkodzie, żeby w jednej pętli prowadzić dwa rekordy naraz: maks i mini. Każda liczba jest porównywana z oboma. Różnica między największą a najmniejszą liczbą ma swoją nazwę — rozstęp — i mówi, jak bardzo dane są „rozrzucone”.

Największa i najmniejsza naraz — animacja
Animacja działa po włączeniu JavaScriptu.
rozstep.cpp
int n;
cin >> n;
vector<int> v(n);
for (auto &x : v) cin >> x;

int maks = v[0], mini = v[0];
for (auto x : v) {
    maks = max(maks, x);
    mini = min(mini, x);
}
cout << "najwieksza: " << maks << "\n";
cout << "najmniejsza: " << mini << "\n";
cout << "rozstep: " << maks - mini << "\n";
▶ Wejście
7 21 45 12 67 8 33 50
▶ Wyjście
najwieksza: 67 najmniejsza: 8 rozstep: 59

Gdy liczby są już w vectorze, start od pierwszej to po prostu v[0]. Pętla „dla każdego” porówna v[0] samo ze sobą — nic się wtedy nie zmieni, więc nie trzeba go pomijać.

Uwaga: v[0] istnieje tylko wtedy, gdy vector nie jest pusty. Jeśli zadanie dopuszcza n = 0, trzeba ten przypadek obsłużyć osobno.

Rekord czegoś, co trzeba policzyć

Rekord nie musi dotyczyć samych wczytanych liczb. Często w każdym obrocie pętli najpierw coś liczysz — długość słowa, sumę cyfr, odległość — a dopiero ten wynik porównujesz z rekordem. Przy długości napisu czeka mała pułapka: s.size() nie jest typu int (to typ bez znaku, który poznałeś w lekcji o vectorze), więc zasada jednego typu każe go zamienić: (int)s.size().

najdluzsze.cpp
vector<string> slowa = {"ala", "programowanie", "kot", "olimpiada"};
int najdl = 0;                        // długość nie bywa ujemna
for (auto s : slowa) {
    najdl = max(najdl, (int)s.size());
}
cout << najdl << "\n";
▶ Wyjście
13
size_zle.cpp
string s = "kot";
int najdl = 0;
najdl = max(najdl, s.size());   // int i size_t — błąd
▶ Kompilator
error: no matching function for call to 'max(int&, std::__cxx11::basic_string<char>::size_type)'

Tu start od zera jest w porządku — długość słowa nigdy nie jest ujemna, więc każde słowo „pobije” zero. Zero jest złe tylko wtedy, gdy wartości mogą być mniejsze od niego.

Rekord tylko z niektórych liczb

Co, jeśli szukasz największej liczby parzystej? Nie możesz zacząć od pierwszej liczby, bo może być nieparzysta. Nie możesz też zacząć od zera, bo parzyste liczby mogą być ujemne. A może parzystych nie ma wcale i trzeba wypisać BRAK? Rozwiązanie: dodatkowa zmienna bool jest, która mówi, czy rekord już istnieje. Pierwsza pasująca liczba zostaje rekordem bez porównywania.

parzysta.cpp
int n;
cin >> n;
bool jest = false;   // czy widzieliśmy już parzystą?
int maks = 0;        // ważne dopiero, gdy jest == true
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x % 2 == 0) {
        if (!jest || x > maks) maks = x;
        jest = true;
    }
}
if (jest) cout << maks << "\n";
else cout << "BRAK\n";
▶ Wejście 1
5 7 -4 3 -10 9
▶ Wyjście 1
-4
▶ Wejście 2
3 1 3 5
▶ Wyjście 2
BRAK

Warunek !jest || x > maks czytaj: „jeszcze nie mamy rekordu albo x jest lepszy od rekordu”. Pierwsza parzysta liczba (−4) wchodzi dzięki lewej części warunku, a każda następna musi już pokonać rekord: −10 nie jest większe od −4, więc wynik to −4.

W drugich danych żadna liczba nie jest parzysta, więc jest zostało false i program wypisał BRAK.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int maks = 5;
int t[4] = {3, 8, 2, 8};
for (int i = 0; i < 4; i++) maks = max(maks, t[i]);
cout << maks;
Pokaż odpowiedź
8Rekord zmienia się tylko raz: przy pierwszej ósemce. Druga ósemka go nie bije.
Co wypisze ten fragment?
int maks = 0;
int t[3] = {-5, -2, -9};
for (int i = 0; i < 3; i++) maks = max(maks, t[i]);
cout << maks;
Pokaż odpowiedź
0Pułapka zera: żadna liczba nie jest większa od 0, więc wynik jest zły — powinno być −2.
Co wypisze ten fragment?
int mini = 100;
vector<int> v = {300, 150, 200};
for (auto x : v) mini = min(mini, x);
cout << mini;
Pokaż odpowiedź
100Ta sama pułapka w drugą stronę: start od 100 jest „lepszy” od wszystkich danych. Poprawnie: 150.
Co wypisze ten fragment?
vector<int> v = {2, 5, 3, 7, 7, 1};
int maks = v[0], zmian = 0;
for (int i = 1; i < 6; i++) {
    if (v[i] > maks) zmian++;
    maks = max(maks, v[i]);
}
cout << maks << " " << zmian;
Pokaż odpowiedź
7 2Rekord zmienia się przy 5 i przy pierwszej 7. Druga 7 nie jest większa od 7.
Co wypisze ten fragment?
vector<string> w = {"ala", "kotek", "pies"};
int d = 0;
for (auto s : w) d = max(d, (int)s.size());
cout << d;
Pokaż odpowiedź
5Najdłuższe jest słowo „kotek”.
Co wypisze ten fragment?
vector<int> v = {4, -1, 7, 2};
int mx = v[0], mn = v[0];
for (auto x : v) { mx = max(mx, x); mn = min(mn, x); }
cout << mx - mn;
Pokaż odpowiedź
8Rozstęp: 7 − (−1) = 8.
Co wypisze ten fragment?
int maks = INT_MIN;
vector<int> v = {-8, -3, -6};
for (auto x : v) maks = max(maks, x);
cout << maks;
Pokaż odpowiedź
-3INT_MIN jest mniejsze od każdej liczby, więc pierwsza liczba od razu zostaje rekordem, a potem wygrywa −3.
Co wypisze ten fragment?
int n = 50731, mn = 9;
while (n > 0) {
    mn = min(mn, n % 10);
    n /= 10;
}
cout << mn;
Pokaż odpowiedź
0Rekord najmniejszej cyfry: cyfry to 1, 3, 7, 0, 5 (od końca). Najmniejsza to 0.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Gdzie był rekord, ile razy padł i kto go ustanowił

Samo max odpowiada tylko na pytanie „ile?”. Zadania często pytają o więcej: na której pozycji stoi największa liczba? Kto zdobył najwięcej punktów? Ile osób ma najlepszy wynik? Do tego potrzebny jest zwykły if, w którym razem z rekordem zapamiętujesz dodatkowe informacje. W tej części nauczysz się też panować nad remisami — sytuacją, gdy rekord występuje kilka razy.

Pozycja rekordu

Wracamy do sędziego: tym razem zapisuje nie tylko długość najlepszego skoku, ale też jego numer. Gdy pada nowy rekord, zmieniają się obie rzeczy naraz — dlatego zamiast max używamy if z dwiema instrukcjami w klamrach.

pozycja.cpp
int n;
cin >> n;
int maks, poz = 1;
cin >> maks;                     // pierwsza liczba ma pozycję 1
for (int i = 2; i <= n; i++) {   // pozycje liczymy od 1
    int x;
    cin >> x;
    if (x > maks) {
        maks = x;
        poz = i;
    }
}
cout << maks << " na pozycji " << poz << "\n";
▶ Wejście
5 3 8 5 8 2
▶ Wyjście
8 na pozycji 2

Zadania zwykle numerują pozycje od 1 („pierwsza liczba, druga liczba…”), a vector i tablica — od 0. Ten program wczytuje liczby bez vectora, więc po prostu liczy pozycje od 1. Gdy dane są w vectorze, pamiętaj o + 1 przy wypisywaniu.

Ósemka występuje dwa razy, a program podał pozycję 2 — pierwsze wystąpienie. Dlaczego? Bo przy drugiej ósemce warunek 8 > 8 jest fałszywy i rekord się nie zmienia.

Pierwsze czy ostatnie wystąpienie? > kontra >=

Jeden znak decyduje, które z równych wystąpień rekordu wygra. Z ostrym > rekord zmienia się tylko na lepszy, więc zostaje pierwsze wystąpienie. Z >= rekord zmienia się także na równy, więc każde kolejne wystąpienie nadpisuje poprzednie i zostaje ostatnie.

pierwsze_ostatnie.cpp
vector<int> v = {3, 8, 5, 8, 2};
int m1 = v[0], p1 = 0;   // z >
int m2 = v[0], p2 = 0;   // z >=
for (int i = 1; i < 5; i++) {
    if (v[i] > m1) { m1 = v[i]; p1 = i; }
    if (v[i] >= m2) { m2 = v[i]; p2 = i; }
}
cout << "pierwsza: " << p1 + 1 << "\n";
cout << "ostatnia: " << p2 + 1 << "\n";
▶ Wyjście
pierwsza: 2 ostatnia: 4
iv[i]z >z >=
188 > 3 → p1 = 18 >= 3 → p2 = 1
25nienie
388 > 8? nie8 >= 8 → p2 = 3
42nienie
Remis przy rekordzie Ostry znak (> dla maksimum, < dla minimum) — wygrywa pierwsze wystąpienie. Znak z równością (>=, <=) — wygrywa ostatnie. Zawsze sprawdź w treści, którego wystąpienia chce zadanie.

Ile razy pojawia się rekord?

Prosty sposób to dwie pętle: pierwsza znajduje rekord, druga liczy, ile liczb jest mu równych. Da się to jednak zrobić w jednej pętli, z licznikiem ile. Gdy pada nowy rekord, licznik zaczyna od 1 — stare wystąpienia gorszego rekordu już się nie liczą. Gdy liczba wyrównuje rekord, licznik rośnie.

ile_razy.cpp
vector<int> v = {3, 8, 5, 8, 2, 8};
int maks = v[0], ile = 1;
for (int i = 1; i < (int)v.size(); i++) {
    if (v[i] > maks) {
        maks = v[i];
        ile = 1;          // nowy rekord — liczymy od nowa
    } else if (v[i] == maks) {
        ile++;            // wyrównany rekord
    }
}
cout << maks << " wystepuje " << ile << " razy\n";
▶ Wyjście
8 wystepuje 3 razy

Prześledź: start maks = 3, ile = 1. Ósemka bije trójkę — maks = 8, ile = 1 (ta jedna trójka przestaje się liczyć). Piątka nic nie zmienia. Druga ósemka wyrównuje — ile = 2. Dwójka nic. Trzecia ósemka — ile = 3.

Najczęstszy błąd: zapomnieć o ile = 1 przy nowym rekordzie. Wtedy licznik pamięta wyrównania starego, gorszego rekordu.

Kto ma rekord?

Wyniki zawodów to zwykle pary: imię i punkty. Zwycięzcę znajdziesz tym samym schematem — obok rekordu punktów trzymasz imię osoby, która go ustanowiła.

zwyciezca.cpp
int n;
cin >> n;
string kto;
int najw;
cin >> kto >> najw;              // pierwszy zawodnik
for (int i = 1; i < n; i++) {
    string imie;
    int pkt;
    cin >> imie >> pkt;
    if (pkt > najw) {
        najw = pkt;
        kto = imie;
    }
}
cout << kto << " " << najw << "\n";
▶ Wejście
4 Ola 17 Kuba 23 Ewa 23 Jan 9
▶ Wyjście
Kuba 23

Kuba i Ewa mają po 23 punkty. Wygrał Kuba, bo był pierwszy, a Ewa tylko wyrównała jego wynik (23 > 23 to fałsz). Gdyby zadanie mówiło „przy remisie wygrywa osoba wpisana później”, wystarczyłoby >=.

A gdyby przy remisie miała wygrać osoba, której imię jest wcześniej w alfabecie? Wtedy warunek rośnie: pkt > najw || (pkt == najw && imie < kto).

Rekord według własnej miary: najbliżej celu

Czasem „najlepsza” nie znaczy „największa”. W zgadywance wygrywa liczba najbliżej celu. Odległość liczby x od celu to abs(x - cel) (z lekcji o parach: abs zabiera minus). Szukamy więc najmniejszej odległości, a przy remisie — powiedzmy — mniejszej liczby.

najblizej.cpp
int cel = 50;
vector<int> v = {38, 61, 44, 56, 70};
int naj = v[0];
for (auto x : v) {
    int d = abs(x - cel), dn = abs(naj - cel);
    if (d < dn || (d == dn && x < naj)) naj = x;
}
cout << naj << "\n";

// to samo parami (odległość, liczba) — porównują się same
pair<int, int> p = {abs(v[0] - cel), v[0]};
for (auto x : v) p = min(p, make_pair(abs(x - cel), x));
cout << p.second << "\n";
▶ Wyjście
44 44
xabs(x − 50)
3812
6111
446 — remis
566 — remis
7020

44 i 56 są tak samo blisko, wygrywa mniejsza: 44. Wersja z parami robi to samo krócej — pary porównują się najpierw po odległości, a przy remisie po samej liczbie. Znasz to z lekcji o parach.

Wszystkie miejsca rekordu

Gdy zadanie chce wszystkich pozycji, na których stoi największa liczba, najprościej zrobić dwa przejścia: najpierw znaleźć rekord, a potem jeszcze raz przejść po danych i wypisać numery liczb równych rekordowi. Do tego dane muszą być w vectorze — drugi raz z wejścia ich nie wczytasz.

wszystkie.cpp
vector<int> v = {4, 9, 2, 9, 9, 1};
int maks = v[0];
for (auto x : v) maks = max(maks, x);       // przejście 1
for (int i = 0; i < (int)v.size(); i++) {   // przejście 2
    if (v[i] == maks) cout << i + 1 << " ";
}
cout << "\n";
▶ Wyjście
2 4 5
Numery od 1. Zielone pudełka to wszystkie wystąpienia rekordu 9: pozycje 2, 4 i 5.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
vector<int> v = {5, 1, 5, 3};
int m = v[0], p = 0;
for (int i = 1; i < 4; i++)
    if (v[i] > m) { m = v[i]; p = i; }
cout << p;
Pokaż odpowiedź
0Druga piątka nie jest większa od pierwszej, więc zostaje pozycja 0.
Co wypisze ten fragment?
vector<int> v = {5, 1, 5, 3};
int m = v[0], p = 0;
for (int i = 1; i < 4; i++)
    if (v[i] >= m) { m = v[i]; p = i; }
cout << p;
Pokaż odpowiedź
2Z >= druga piątka wyrównuje rekord i nadpisuje pozycję.
Co wypisze ten fragment?
vector<int> v = {4, 2, 7, 2};
int m = v[0], p = 0;
for (int i = 1; i < 4; i++)
    if (v[i] < m) { m = v[i]; p = i; }
cout << m << " " << p;
Pokaż odpowiedź
2 1Najmniejsza to 2. Z ostrym < zostaje pierwsze wystąpienie: pozycja 1.
Co wypisze ten fragment?
vector<int> v = {6, 2, 6, 6, 3};
int m = v[0], ile = 1;
for (int i = 1; i < 5; i++) {
    if (v[i] > m) { m = v[i]; ile = 1; }
    else if (v[i] == m) ile++;
}
cout << ile;
Pokaż odpowiedź
3Szóstka jest rekordem od początku i wyrównuje się dwa razy: 1 + 2 = 3.
Co wypisze ten fragment?
vector<string> im = {"Ala", "Bob", "Cyd"};
vector<int> pkt = {7, 9, 9};
int b = 0;
for (int i = 1; i < 3; i++)
    if (pkt[i] > pkt[b]) b = i;
cout << im[b];
Pokaż odpowiedź
BobWystarczy pamiętać numer zwycięzcy. Cyd tylko wyrównuje wynik Boba.
Ktoś zapomniał o ile = 1. Co wypisze program?
vector<int> v = {2, 2, 5};
int m = v[0], ile = 1;
for (int i = 1; i < 3; i++) {
    if (v[i] > m) m = v[i];
    else if (v[i] == m) ile++;
}
cout << m << " " << ile;
Pokaż odpowiedź
5 2Licznik zapamiętał dwie dwójki, choć rekordem jest 5, która występuje raz. Poprawnie: 5 1.
Co wypisze ten fragment?
int cel = 10, naj = 7;
vector<int> v = {7, 13, 12};
for (auto x : v)
    if (abs(x - cel) < abs(naj - cel)) naj = x;
cout << naj;
Pokaż odpowiedź
12Odległości: 3, 3 i 2. Najbliżej jest 12.
Co wypisze ten fragment?
vector<int> v = {9, 4, 4};
pair<int, int> b = {v[0], 0};
for (int i = 0; i < 3; i++) b = min(b, make_pair(v[i], i));
cout << b.first << " " << b.second;
Pokaż odpowiedź
4 1Para (wartość, numer): przy remisie wartości wygrywa mniejszy numer, więc pierwsza czwórka.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

max_element i min_element — rekord bez pętli

Gdy dane siedzą już w vectorze, tablicy albo napisie, pętli z rekordem nie musisz pisać sam. C++ ma gotowe polecenia max_element i min_element, które poznałeś przelotnie w lekcji o vectorze. Teraz przyjrzymy się im dokładnie: jak odczytać z nich wartość i pozycję, jak użyć ich na tablicy, na kawałku danych i na napisie, jak znaleźć oba skrajne elementy naraz i jak szukać rekordu według własnej reguły.

Strzałka na rekord

max_element(v.begin(), v.end()) przegląda vector od pierwszej strzałki do drugiej i oddaje strzałkę (iterator) na największy element — nie samą liczbę. Ze strzałki wyciągasz dwie rzeczy, tak jak w lekcji o vectorze: gwiazdka * daje wartość, na którą strzałka pokazuje, a odjęcie v.begin() daje numer pudełka. Gdy największych jest kilka, strzałka pokazuje pierwszy z nich.

max_element pokazuje pierwszą dziewiątkę (pudełko 1), a min_element — jedynkę (pudełko 4). Druga dziewiątka (pudełko 3) przegrywa, bo jest dalej.
element.cpp
vector<int> v = {4, 9, 2, 9, 1};
cout << *max_element(v.begin(), v.end()) << "\n";              // wartość
cout << *min_element(v.begin(), v.end()) << "\n";
cout << max_element(v.begin(), v.end()) - v.begin() << "\n";   // numer
cout << min_element(v.begin(), v.end()) - v.begin() << "\n";
▶ Wyjście
9 1 1 4

Pierwsze dwa wiersze to wartości: największa 9, najmniejsza 1.

Dwa kolejne to numery pudełek, liczone od 0: dziewiątka stoi w pudełku 1, jedynka w pudełku 4. Jeśli zadanie numeruje pozycje od 1, dodaj 1.

Bez gwiazdki cout nie wypisze wartości — strzałka to nie liczba i program się nie skompiluje.

Tablica, kawałek i napis

Te same polecenia działają na zwykłej tablicy — z tymi samymi strzałkami co w sort(t, t + n): max_element(t, t + n). Numer dostajesz wtedy, odejmując t. Działają też na kawałku danych: strzałki nie muszą obejmować całości. I działają na napisie, bo napis to rząd znaków.

tablica_kawalek.cpp
int t[6] = {7, -3, 12, 5, 12, 0};
int n = 6;
cout << *max_element(t, t + n) << " " << *min_element(t, t + n) << "\n";
cout << max_element(t, t + n) - t << "\n";       // numer w tablicy

vector<int> v = {8, 1, 6, 3, 9, 2};
int a = 1, b = 3;                                // pudełka 1..3
cout << *max_element(v.begin() + a, v.begin() + b + 1) << "\n";
cout << max_element(v.begin() + a, v.begin() + b + 1) - v.begin() << "\n";

string s = "programowanie";
cout << *max_element(s.begin(), s.end()) << *min_element(s.begin(), s.end()) << "\n";
▶ Wyjście
12 -3 2 6 2 wa

W tablicy 12 występuje dwa razy — numer 2 to pierwsze wystąpienie.

Kawałek od pudełka 1 do 3 to liczby 1, 6, 3. Największa jest szóstka. Uwaga: numer liczymy od v.begin(), a nie od początku kawałka, więc dostajemy prawdziwy numer pudełka w vectorze — 2. Druga strzałka ma + 1, bo pokazuje miejsce, którego już nie bierzemy.

W napisie „programowanie” najdalej w alfabecie jest litera w, a najwcześniej a.

Ile razy? count na pomoc

Z lekcji o vectorze znasz też count(v.begin(), v.end(), x) — liczy, ile razy x występuje w vectorze. Razem z max_element daje odpowiedź na pytanie z części 4 w dwóch linijkach:

count.cpp
vector<int> v = {3, 7, 7, 1, 7};
int mx = *max_element(v.begin(), v.end());
cout << mx << " x" << count(v.begin(), v.end(), mx) << "\n";
▶ Wyjście
7 x3

To dwa przejścia po danych (jedno w max_element, drugie w count), ale kod jest krótki i trudno się w nim pomylić. Przy danych do kilkuset tysięcy liczb to żaden problem.

Oba naraz: minmax_element

minmax_element w jednym przejściu znajduje oba skrajne elementy i oddaje parę strzałek: first pokazuje najmniejszy, a second największy. Parę wygodnie rozpakować tak jak w lekcji o parach: auto [lo, hi] = …. Jest jeden haczyk, który warto znać: przy remisie lo pokazuje pierwszy najmniejszy, ale hi — ostatni największy.

minmax_element.cpp
vector<int> v = {5, 1, 9, 1, 9};
auto [lo, hi] = minmax_element(v.begin(), v.end());
cout << *lo << " " << *hi << "\n";
cout << lo - v.begin() << " " << hi - v.begin() << "\n";
▶ Wyjście
1 9 1 4

Najmniejsza jedynka: pierwsza, z pudełka 1. Największa dziewiątka: ostatnia, z pudełka 4 — a nie z pudełka 2, jak przy max_element. Jeśli w zadaniu liczy się pozycja, sprawdź, którego wystąpienia potrzebujesz.

Rekord według własnej reguły

Pamiętasz z lekcji o sortowaniu regułę porównania — lambdę, która odpowiada na pytanie „czy a jest przed b?”. max_element i min_element też ją przyjmują jako trzeci argument. Reguła odpowiada wtedy na pytanie „czy a jest mniejsze od b?” — dokładnie tak samo jak w sort. Najdłuższe słowo? Reguła: „a jest mniejsze od b, gdy jest krótsze”.

regula.cpp
vector<string> w = {"kot", "zebra", "pies", "tygrys", "jaguar"};
auto it = max_element(w.begin(), w.end(), [](string a, string b) {
    return a.size() < b.size();     // krótsze = mniejsze
});
cout << *it << " " << it - w.begin() << "\n";

vector<int> v = {-7, 3, 5, -2};
cout << *max_element(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);         // dalej od zera = większe
}) << "\n";
▶ Wyjście
tygrys 3 -7

„tygrys” i „jaguar” mają po 6 liter. Wygrywa pierwszy z nich — max_element zawsze oddaje pierwszy z równych.

W drugim przykładzie „największa” jest liczba najdalej od zera, czyli o największej wartości bezwzględnej: −7.

Reguła musi zwracać false dla równych elementów, więc piszemy <, nigdy <= — zasada z lekcji o sortowaniu.

Pętla czy gotowiec?

sytuacjaco wybrać
liczby wczytujesz po kolei i nie musisz ich pamiętaćpętla z rekordem — nie trzeba vectora
dane są w vectorze, tablicy albo napisie, chcesz wartości albo numerumax_element / min_element
potrzebujesz kilku rzeczy naraz (rekord, kto, ile razy, druga największa…)pętla z if — pełna kontrola
„największy” według własnej miarymax_element z regułą albo pętla z parą
Pusty vector Na pustym vectorze max_element oddaje v.end() — strzałkę za ostatnim elementem, za którym nic nie ma. Gwiazdka przeczyta wtedy śmieci spoza vectora (tak jak v[0] w pustym vectorze). Jeśli dane mogą być puste, sprawdź to najpierw: if (v.empty()).
Sprawdź się w głowie

Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
vector<int> v = {3, 8, 1};
cout << *max_element(v.begin(), v.end());
Pokaż odpowiedź
8Gwiazdka daje wartość największego elementu.
Co wypisze ten fragment?
vector<int> v = {3, 8, 1, 1};
cout << min_element(v.begin(), v.end()) - v.begin();
Pokaż odpowiedź
2Najmniejsza jedynka stoi pierwszy raz w pudełku 2.
Co wypisze ten fragment?
int t[5] = {2, 9, 4, 9, 0};
cout << max_element(t, t + 5) - t;
Pokaż odpowiedź
1Pierwsza dziewiątka — pudełko 1.
Co wypisze ten fragment?
int t[4] = {1, 5, 2, 8};
cout << *max_element(t, t + 3);
Pokaż odpowiedź
5Przeglądamy tylko pudełka 0, 1, 2 — ósemka jest poza zakresem.
Co wypisze ten fragment?
string s = "Ala";
cout << *max_element(s.begin(), s.end());
Pokaż odpowiedź
lKody: 'A' = 65, 'l' = 108, 'a' = 97. Największy ma 'l'.
Co wypisze ten fragment?
vector<int> v = {2, 2, 5, 5};
auto [lo, hi] = minmax_element(v.begin(), v.end());
cout << lo - v.begin() << " " << hi - v.begin();
Pokaż odpowiedź
0 3minmax_element: pierwszy najmniejszy (pudełko 0) i ostatni największy (pudełko 3).
Co wypisze ten fragment?
vector<int> v = {4, -9, 6};
cout << *min_element(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);
});
Pokaż odpowiedź
4Najbliżej zera (najmniejsza wartość bezwzględna) jest 4.
Co wypisze ten fragment?
vector<int> v = {1, 4, 4, 2};
cout << count(v.begin(), v.end(), *max_element(v.begin(), v.end()));
Pokaż odpowiedź
2Największa to 4, a występuje dwa razy.
Ćwiczenia · teraz Ty

7 ćwiczeń do tej części

0 / 7 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Nie mniej niż, nie więcej niż — przycinanie i przedziały

Do tej pory max i min szukały rekordów. Teraz poznasz ich drugie, równie częste zastosowanie: pilnowanie granic. Punkty życia w grze nie spadają poniżej zera, bateria nie naładuje się ponad 100%, a szklanka nie pomieści więcej wody, niż ma pojemności. Każde takie „nie mniej niż” i „nie więcej niż” to jedno max albo min. Na koniec użyjemy tego samego pomysłu do przedziałów: gdzie zaczyna się i kończy ich wspólna część.

Podłoga: max(0, x)

Postać w grze ma 30 punktów życia i dostaje 45 obrażeń. Ile ma życia? Matematycznie 30 − 45 = −15, ale w grze nie ma ujemnego życia — jest zero. Zapis max(0, hp - obrazenia) robi z zera podłogę: jeśli wynik jest dodatni, zostaje bez zmian; jeśli spadłby poniżej zera, max wybierze zero.

podloga.cpp
int hp = 30;
hp = max(0, hp - 12);   // 18 — normalnie
cout << hp << "\n";
hp = max(0, hp - 45);   // -27 → 0
cout << hp << "\n";
▶ Wyjście
18 0

Czytaj max(0, x) jako „x, ale nie mniej niż 0”. To samo zrobiłbyś if-em: if (hp < 0) hp = 0; — ale tu wszystko mieści się w jednej linijce z odejmowaniem.

Podłoga nie musi być zerem. „Ocena nie niższa niż 1” to max(1, ocena).

Sufit: min(limit, x)

W drugą stronę działa min. Bateria ma 85% i ładujesz ją o 30 punktów procentowych — nie będzie 115%, tylko 100%. Zapis min(100, bateria + 30) robi z setki sufit: „bateria + 30, ale nie więcej niż 100”.

Sufit przydaje się też, gdy coś ma ograniczoną pojemność. Przelewasz wodę z dzbanka do szklanki: przeleje się tyle, ile jest w dzbanku, ale nie więcej, niż zmieści się w szklance. Ile się zmieści? Pojemność minus to, co już jest w środku.

sufit.cpp
int bateria = 85;
bateria = min(100, bateria + 30);
cout << bateria << "\n";

int dzbanek = 700, szklanka = 150, pojemnosc = 250;
int ile = min(dzbanek, pojemnosc - szklanka);   // ile się przeleje
dzbanek -= ile;
szklanka += ile;
cout << ile << " " << dzbanek << " " << szklanka << "\n";
▶ Wyjście
100 100 600 250

W szklance jest 150 ml, a mieści się 250 ml, więc wolnego miejsca jest 100 ml. W dzbanku jest dużo więcej (700 ml), więc przelewa się tylko 100 ml i szklanka jest pełna.

Gdyby w dzbanku było tylko 60 ml, min(60, 100) dałoby 60 — przelałaby się cała woda z dzbanka.

Podłoga i sufit naraz: przycinanie

Gdy wartość ma się mieścić między dwiema granicami — od lo do hi — składamy oba pomysły: max(lo, min(hi, x)). Czytamy od środka: min(hi, x) ścina wszystko powyżej górnej granicy, a max(lo, …) podnosi wszystko poniżej dolnej. Takie działanie nazywa się przycinaniem (po angielsku clamp), i od C++17 jest na nie gotowa funkcja clamp(x, lo, hi). Uwaga na kolejność: w clamp najpierw idzie wartość, potem dolna i górna granica.

przycinanie.cpp
vector<int> zmiany = {150, -30, 42, 100, 0};
for (int x : zmiany) {
    int a = max(0, min(100, x));
    int b = clamp(x, 0, 100);      // to samo gotowcem
    cout << x << " -> " << a << " " << b << "\n";
}
▶ Wyjście
150 -> 100 100 -30 -> 0 0 42 -> 42 42 100 -> 100 100 0 -> 0 0
xmin(100, x)max(0, …)
150100100
−30−300
424242

Fioletowe wartości to miejsca, w których granica „zadziałała”. Liczba 42 mieści się w przedziale, więc przechodzi bez zmian.

Pomylone granice Częsty błąd to zamiana miejscami: min(0, max(100, x)). Wtedy max(100, x) daje co najmniej 100, a min(0, …) zawsze 0 — każda liczba zamienia się w zero. Zapamiętaj: przy dolnej granicy stoi max (podłoga podnosi), przy górnej — min (sufit obniża).

Wspólna część dwóch przedziałów

Ola ma czas od 14 do 18, a Kuba od 16 do 20. Kiedy oboje mają czas? Wspólna część zaczyna się wtedy, gdy oboje już zaczęli — czyli w późniejszym z początków: max(14, 16) = 16. Kończy się, gdy ktoś pierwszy skończy — we wcześniejszym z końców: min(18, 20) = 18. Jeśli wyszło, że początek jest za końcem, wspólnej części nie ma. Znasz to już z lekcji o parach — teraz policzymy jeszcze jej długość.

wspolna.cpp
int a1, b1, a2, b2;
cin >> a1 >> b1 >> a2 >> b2;
int od = max(a1, a2);
int doo = min(b1, b2);
cout << "od " << od << " do " << doo << "\n";
cout << "dlugosc: " << max(0, doo - od) << "\n";
▶ Wejście 1
14 18 16 20
▶ Wyjście 1
od 16 do 18 dlugosc: 2
▶ Wejście 2
2 5 8 12
▶ Wyjście 2
od 8 do 5 dlugosc: 0

Za drugim razem przedziały [2, 5] i [8, 12] się rozmijają: „wspólna część” od 8 do 5 nie istnieje, bo zaczyna się za swoim końcem. Długość 5 − 8 = −3 nie ma sensu — i tu znowu pomaga podłoga: max(0, doo - od) zamienia każdą ujemną długość na zero.

Zmienna nazywa się doo, bo do jest w C++ zajęte — to słowo z pętli do … while.

Wspólna część przedziałów Początek: max początków. Koniec: min końców. Długość: max(0, koniec - początek). Dla wielu przedziałów naraz: początek to największy ze wszystkich początków, koniec — najmniejszy ze wszystkich końców (czyli dwa rekordy w jednej pętli).

Dwa prostokąty na planszy

Ten sam pomysł działa w dwóch wymiarach. Prostokąt o bokach równoległych do osi to po prostu dwa przedziały: jeden na osi x (od lewej do prawej krawędzi) i jeden na osi y (od dołu do góry). Część wspólna dwóch prostokątów to prostokąt, którego szerokość jest wspólną częścią przedziałów x, a wysokość — wspólną częścią przedziałów y. Pole = szerokość · wysokość.

prostokaty.cpp
// prostokąt: lewy dolny róg (x1, y1), prawy górny (x2, y2)
long long ax1 = 0, ay1 = 0, ax2 = 6, ay2 = 4;   // prostokąt A
long long bx1 = 3, by1 = 2, bx2 = 9, by2 = 7;   // prostokąt B
long long szer = max(0LL, min(ax2, bx2) - max(ax1, bx1));
long long wys = max(0LL, min(ay2, by2) - max(ay1, by1));
cout << szer << " " << wys << " " << szer * wys << "\n";
▶ Wyjście
3 2 6

Na osi x: [0, 6] i [3, 9] mają wspólne [3, 6], czyli szerokość 3. Na osi y: [0, 4] i [2, 7] mają wspólne [2, 4], czyli wysokość 2. Pole wspólnej części: 3 · 2 = 6.

Używamy long long, bo współrzędne mogą być duże, a pole to iloczyn. Stąd 0LL w max — zasada jednego typu.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int hp = 20;
hp = max(0, hp - 7);
hp = max(0, hp - 15);
cout << hp;
Pokaż odpowiedź
020 − 7 = 13, potem 13 − 15 = −2, a max(0, −2) = 0.
Co wypisze ten fragment?
int b = 90;
b = min(100, b + 5);
b = min(100, b + 5);
b = min(100, b + 5);
cout << b;
Pokaż odpowiedź
10095, potem 100, a potem min(100, 105) = 100.
Co wypisze ten fragment?
cout << clamp(17, 0, 10) << " " << clamp(-3, 0, 10);
Pokaż odpowiedź
10 017 jest powyżej sufitu 10, a −3 poniżej podłogi 0.
Co wypisze ten fragment?
int x = 55;
cout << max(10, min(50, x));
Pokaż odpowiedź
50Najpierw min(50, 55) = 50, potem max(10, 50) = 50.
Co wypisze ten fragment z pomylonymi granicami?
int x = 42;
cout << min(0, max(100, x));
Pokaż odpowiedź
0max(100, 42) = 100, a min(0, 100) = 0. Pomylone granice zamieniają wszystko w zero.
Ile wynosi długość wspólnej części?
int a1 = 3, b1 = 10, a2 = 7, b2 = 15;
cout << max(0, min(b1, b2) - max(a1, a2));
Pokaż odpowiedź
3Wspólna część to [7, 10], długość 3.
Ile wynosi długość wspólnej części?
int a1 = 1, b1 = 4, a2 = 6, b2 = 9;
cout << max(0, min(b1, b2) - max(a1, a2));
Pokaż odpowiedź
0min(4, 9) − max(1, 6) = 4 − 6 = −2 — przedziały się rozmijają, więc 0.
Ile się przeleje?
int dzbanek = 40, szklanka = 180, poj = 250;
cout << min(dzbanek, poj - szklanka);
Pokaż odpowiedź
40W szklance jest jeszcze 70 ml miejsca, ale w dzbanku tylko 40 ml — przeleje się wszystko.
Ćwiczenia · teraz Ty

7 ćwiczeń do tej części

0 / 7 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Dwie największe w jednym przejściu

Na zawodach nie liczy się tylko zwycięzca — jest też drugie i trzecie miejsce. Jak znaleźć drugą największą liczbę? Jeden sposób już znasz: posortować malejąco i wziąć v[1]. Działa, ale miesza kolejność danych i wymaga trzymania ich wszystkich w vectorze. W tej części poznasz sposób bez sortowania: dwa rekordy naraz, które w jednym przejściu pilnują złota i srebra. Potem użyjemy go do najlepszej pary, największego iloczynu i całego podium.

Złoto i srebro: m1 i m2

Trzymamy dwie zmienne: m1 — największa liczba do tej pory (złoto) i m2 — druga największa (srebro). Przychodzi nowa liczba x. Są trzy możliwości:

1) x jest większa od złota — nowa mistrzyni! Dotychczasowe złoto nie znika, tylko spada na srebro: najpierw m2 = m1, dopiero potem m1 = x.
2) x nie bije złota, ale jest większa od srebra — zabiera srebro: m2 = x.
3) x nie bije nikogo — nic się nie zmienia.

Dwie największe w jednym przejściu — animacja
Animacja działa po włączeniu JavaScriptu.
dwie_najwieksze.cpp
int n;
cin >> n;
int m1 = INT_MIN, m2 = INT_MIN;   // złoto i srebro
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x > m1) {
        m2 = m1;        // stare złoto spada na srebro
        m1 = x;
    } else if (x > m2) {
        m2 = x;
    }
}
cout << m1 << " " << m2 << "\n";
▶ Wejście
7 12 45 7 45 30 51 8
▶ Wyjście
51 45
xco się dziejem1m2
12bije złoto (INT_MIN)12INT_MIN
45bije złoto — 12 spada4512
7nikogo nie bije4512
45nie bije złota, bije srebro4545
30nikogo nie bije4545
51bije złoto — 45 spada5145
8nikogo nie bije5145
Kolejność ma znaczenie Jeśli napiszesz m1 = x; m2 = m1;, to w drugiej linijce m1 jest już nowe — i obie zmienne dostają x. Stare złoto przepada. Zawsze najpierw przesuwaj w dół (m2 = m1), a dopiero potem wpisuj nową wartość na górę.

Druga największa — licząc powtórzenia czy nie?

Dla liczb 9, 9, 5 program powyżej odpowie: m1 = 9, m2 = 9. Czy to dobrze? To zależy od treści zadania. Jeśli pyta o „dwie największe liczby z listy” (np. dwa najlepsze wyniki) — tak, druga dziewiątka to osobny wynik. Jeśli pyta o „drugą największą wartość” albo „drugą największą różną liczbę” — odpowiedź to 5. Wtedy liczbę równą złotu trzeba pominąć: srebro dostaje tylko liczba mniejsza od złota.

druga_rozna.cpp
vector<int> v = {9, 9, 5};
int m1 = INT_MIN, m2 = INT_MIN;     // z powtórzeniami
int r1 = INT_MIN, r2 = INT_MIN;     // różne wartości
for (auto x : v) {
    if (x > m1) { m2 = m1; m1 = x; }
    else if (x > m2) m2 = x;

    if (x > r1) { r2 = r1; r1 = x; }
    else if (x < r1 && x > r2) r2 = x;   // równa złotu — pomijamy
}
cout << m1 << " " << m2 << "\n";
cout << r1 << " " << r2 << "\n";
▶ Wyjście
9 9 9 5

Różnica jest tylko w jednym warunku: x < r1 && x > r2. Druga dziewiątka nie jest mniejsza od złota, więc nie wchodzi na srebro.

A jeśli wszystkie liczby są równe? Wtedy różnej drugiej wartości po prostu nie ma — r2 zostaje równe INT_MIN i po tym poznasz, że trzeba wypisać na przykład BRAK.

Najlepsza para: suma i iloczyn

Największa suma dwóch różnych elementów to po prostu m1 + m2 — dwie największe liczby razem. Z iloczynem jest ciekawiej, bo minus razy minus daje plus. Dwie bardzo „duże” liczby ujemne, np. −10 i −8, dają iloczyn 80, większy niż iloczyn dwóch największych dodatnich. Dlatego kandydatów jest dwóch: iloczyn dwóch największych i iloczyn dwóch najmniejszych. Wynikiem jest większy z nich.

iloczyn.cpp
vector<long long> v = {-10, -8, 1, 3, 5};
long long m1 = LLONG_MIN, m2 = LLONG_MIN;   // dwie największe
long long s1 = LLONG_MAX, s2 = LLONG_MAX;   // dwie najmniejsze
for (auto x : v) {
    if (x > m1) { m2 = m1; m1 = x; }
    else if (x > m2) m2 = x;
    if (x < s1) { s2 = s1; s1 = x; }
    else if (x < s2) s2 = x;
}
cout << "suma: " << m1 + m2 << "\n";
cout << "iloczyn: " << max(m1 * m2, s1 * s2) << "\n";
▶ Wyjście
suma: 8 iloczyn: 80

Dwie największe: 5 i 3 — suma 8, iloczyn 15. Dwie najmniejsze: −10 i −8 — iloczyn 80. Wygrywa 80.

Dwie najmniejsze szukamy tym samym schematem, tylko ze znakiem < i startem od LLONG_MAX.

Iloczyn dwóch liczb rzędu miliarda to już 1018 — dlatego long long.

Całe podium: trzy największe

Schemat rozszerza się na trzy miejsca bez nowych pomysłów — jest tylko dłuższy łańcuch przesunięć. Gdy x bije złoto, wszyscy spadają o jedno miejsce: brąz dostaje srebro, srebro dostaje złoto. Gdy bije tylko srebro — przesuwa się srebro na brąz. Gdy bije tylko brąz — zabiera brąz.

podium.cpp
vector<int> v = {40, 75, 62, 90, 75, 18};
int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
for (auto x : v) {
    if (x > m1) { m3 = m2; m2 = m1; m1 = x; }
    else if (x > m2) { m3 = m2; m2 = x; }
    else if (x > m3) { m3 = x; }
}
cout << m1 << " " << m2 << " " << m3 << "\n";
▶ Wyjście
90 75 75

Przy dwóch, trzech miejscach takie rekordy są wygodne i szybkie. Gdy zadanie pyta o dziesięć najlepszych albo o k-tą największą liczbę dla dowolnego k, łańcuch zrobiłby się za długi — wtedy wracamy do sortowania z poprzedniej lekcji: sort malejąco i v[k - 1].

Sprawdź się w głowie

Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
vector<int> v = {5, 9, 7};
int m1 = INT_MIN, m2 = INT_MIN;
for (auto x : v) {
    if (x > m1) { m2 = m1; m1 = x; }
    else if (x > m2) m2 = x;
}
cout << m1 << " " << m2;
Pokaż odpowiedź
9 75 jest złotem, 9 zabiera złoto (5 spada), 7 bije srebro (5).
Co wypisze ten fragment z pomyloną kolejnością?
int m1 = 1, m2 = 0;
int x = 8;
if (x > m1) { m1 = x; m2 = m1; }
cout << m1 << " " << m2;
Pokaż odpowiedź
8 8m1 dostało 8, a potem m2 skopiowało już nowe m1. Stare złoto (1) przepadło.
Co wypisze ten fragment?
vector<int> v = {6, 6, 2};
int m1 = INT_MIN, m2 = INT_MIN;
for (auto x : v) {
    if (x > m1) { m2 = m1; m1 = x; }
    else if (x > m2) m2 = x;
}
cout << m1 << " " << m2;
Pokaż odpowiedź
6 6Druga szóstka nie bije złota, ale bije srebro — powtórzenia się liczą.
Co wypisze ten fragment?
vector<int> v = {6, 6, 2};
int m1 = INT_MIN, m2 = INT_MIN;
for (auto x : v) {
    if (x > m1) { m2 = m1; m1 = x; }
    else if (x < m1 && x > m2) m2 = x;
}
cout << m1 << " " << m2;
Pokaż odpowiedź
6 2Druga szóstka nie jest mniejsza od złota, więc ją pomijamy. Srebro zdobywa 2.
Jaki jest największy iloczyn dwóch liczb?
long long a = 2 * 1, b = (-5) * (-4);
cout << max(a, b);
Pokaż odpowiedź
20Dla liczb −5, −4, 1, 2: dwie największe dają 2, dwie najmniejsze — 20.
Co wypisze ten fragment?
vector<int> v = {7, 3, 9, 3};
int s1 = INT_MAX, s2 = INT_MAX;
for (auto x : v) {
    if (x < s1) { s2 = s1; s1 = x; }
    else if (x < s2) s2 = x;
}
cout << s1 + s2;
Pokaż odpowiedź
6Dwie najmniejsze to 3 i 3.
Co wypisze ten fragment?
vector<int> v = {4, 1, 8, 6, 2};
int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
for (auto x : v) {
    if (x > m1) { m3 = m2; m2 = m1; m1 = x; }
    else if (x > m2) { m3 = m2; m2 = x; }
    else if (x > m3) m3 = x;
}
cout << m3;
Pokaż odpowiedź
4Podium: 8, 6, 4. Brąz to 4.
Co wypisze ten fragment?
vector<int> v = {3, 9, 9, 1};
sort(v.rbegin(), v.rend());
cout << v[1];
Pokaż odpowiedź
9Po sortowaniu malejąco: 9 9 3 1. Pod numerem 1 stoi druga dziewiątka.
Ćwiczenia · teraz Ty

7 ćwiczeń do tej części

0 / 7 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Rekordy na bieżąco, widok z prawej i najlepszy zysk

Do tej pory rekord był ważny dopiero na końcu, po obejrzeniu wszystkich liczb. A przecież w trakcie pętli on też coś znaczy: po każdym kroku mówi, jaki jest rekord do tej pory. W tej części wykorzystamy te pośrednie wartości: wypiszemy rekordy dzień po dniu, policzymy, ile razy rekord został pobity, spojrzymy na dane od prawej strony, a na koniec rozwiążemy słynne zadanie o kupnie i sprzedaży akcji.

Rekord dzień po dniu

Biegacz notuje wyniki kolejnych treningów (powiedzmy, ile kilometrów przebiegł). Po każdym treningu chce wiedzieć, jaki jest jego rekord życiowy i czy właśnie go pobił. Wystarczy wypisywać rekord w środku pętli, po każdej aktualizacji. Taki ciąg rekordów nazywa się maksimum prefiksowym — prefiks to początek ciągu, a my po każdym kroku znamy maksimum początku od pierwszej liczby do bieżącej.

Rekordy na bieżąco — animacja
Animacja działa po włączeniu JavaScriptu.
na_biezaco.cpp
int n;
cin >> n;
int rekord = INT_MIN, ile = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x > rekord) ile++;      // rekord pobity!
    rekord = max(rekord, x);
    cout << rekord << " ";      // rekord do tej pory
}
cout << "\n";
cout << "rekord bity " << ile << " razy\n";
▶ Wejście
8 3 7 5 9 4 9 12 2
▶ Wyjście
3 7 7 9 9 9 12 12 rekord bity 4 razy

Pierwszy wynik zawsze jest rekordem — dlatego start od INT_MIN: pierwsza liczba na pewno go pobije i zostanie policzona.

Rekord padał przy 3, 7, 9 i 12. Druga dziewiątka tylko go wyrównała (9 > 9 to fałsz), więc się nie liczy.

Zauważ, że wypisany ciąg nigdy nie maleje — rekord może tylko rosnąć albo stać w miejscu.

Tablica rekordów: od lewej i od prawej

Czasem rekordy trzeba nie tylko wypisać, ale zapamiętać, żeby później z nich korzystać. Wtedy zapisujemy je do vectora pm: pm[i] to największa liczba wśród a[0]…a[i]. Każdy kolejny element liczymy z poprzedniego: pm[i] = max(pm[i - 1], a[i]). Tak samo da się iść od prawej: sm[i] to największa liczba wśród a[i]…a[n - 1], a liczymy ją pętlą od końca: sm[i] = max(sm[i + 1], a[i]).

pm_sm.cpp
vector<int> a = {3, 7, 5, 9, 4, 2};
int n = a.size();
vector<int> pm(n), sm(n);
pm[0] = a[0];
for (int i = 1; i < n; i++) pm[i] = max(pm[i - 1], a[i]);
sm[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; i--) sm[i] = max(sm[i + 1], a[i]);
for (auto x : pm) cout << x << " ";
cout << "\n";
for (auto x : sm) cout << x << " ";
cout << "\n";
▶ Wyjście
3 7 7 9 9 9 9 9 9 9 4 2
pm[i] — największa od lewej do i. sm[i] — największa od i do prawej. pm[3] = 9, bo wśród 3, 7, 5, 9 największa jest 9; sm[4] = 4, bo wśród 4, 2 największa jest 4.

Po co to? Mając obie tablice, dla każdego miejsca i od razu wiesz, jaka jest największa liczba na lewo i na prawo od niego — bez przeglądania danych od nowa. To ważne: gdybyś dla każdego i szukał maksimum osobną pętlą, wyszłaby pętla w pętli, czyli około n·n kroków. Z tablicami pm i sm to tylko trzy zwykłe pętle.

Widok z prawej

W rzędzie stoją budynki o różnych wysokościach. Patrzysz na nie z prawej strony, z bardzo daleka. Który budynek widzisz? Ten, który jest wyższy od wszystkich budynków na prawo od niego — niższe zasłania coś bliżej Ciebie. Idziemy więc od prawej do lewej z rekordem maksPrawo (najwyższy budynek po prawej) i sprawdzamy, czy bieżący budynek go bije.

widok.cpp
vector<int> h = {4, 9, 3, 7, 2, 5, 1};
int maksPrawo = INT_MIN, widac = 0;
for (int i = (int)h.size() - 1; i >= 0; i--) {
    if (h[i] > maksPrawo) {
        widac++;
        cout << "widac budynek " << i + 1 << " (wysokosc " << h[i] << ")\n";
    }
    maksPrawo = max(maksPrawo, h[i]);
}
cout << widac << "\n";
▶ Wyjście
widac budynek 7 (wysokosc 1) widac budynek 6 (wysokosc 5) widac budynek 4 (wysokosc 7) widac budynek 2 (wysokosc 9) 4
Patrzymy od prawej. Zielone budynki widać. Budynek 5 (wysokość 2) chowa się za budynkiem 6 (wysokość 5), budynek 3 — za budynkiem 4 (wysokość 7), a budynek 1 — za budynkiem 2 (wysokość 9).

To ten sam schemat co „rekord bity”, tylko pętla idzie od końca. Budynek jest widoczny dokładnie wtedy, gdy bije rekord liczony od prawej.

Najlepszy zysk: kup tanio, sprzedaj drogo

Znasz ceny akcji z n kolejnych dni. Możesz kupić jedną akcję w jednym dniu i sprzedać ją w którymś późniejszym. Jaki największy zysk da się osiągnąć? Sprawdzanie wszystkich par dni (kupno, sprzedaż) to pętla w pętli. Sprytniej: idziemy dzień po dniu i zakładamy, że sprzedajemy dzisiaj. Kiedy najlepiej było kupić? Oczywiście najtaniej — a najniższą cenę z dni wcześniejszych pamięta rekord mini. Zysk przy sprzedaży dziś to cena - mini, a najlepszy zysk to rekord tych wartości.

Najlepszy zysk — animacja
Animacja działa po włączeniu JavaScriptu.
zysk.cpp
int n;
cin >> n;
int mini = INT_MAX, zysk = 0;
for (int i = 0; i < n; i++) {
    int cena;
    cin >> cena;
    zysk = max(zysk, cena - mini);   // 1. sprzedaż dziś
    mini = min(mini, cena);          // 2. potem dopisz dzisiejszą cenę
}
cout << zysk << "\n";
▶ Wejście 1
6 7 1 5 3 6 4
▶ Wyjście 1
5
▶ Wejście 2
5 9 7 4 3 1
▶ Wyjście 2
0

Najlepiej kupić w dniu 1 po 1 i sprzedać w dniu 4 po 6: zysk 5.

W drugich danych ceny tylko spadają — każda sprzedaż przyniosłaby stratę, więc najlepiej nie kupować wcale. Zysk 0 to start rekordu: „nic nie robię”.

Kolejność linijek w pętli ma znaczenie: najpierw liczymy sprzedaż, a dopiero potem dopisujemy dzisiejszą cenę do minimum. Dzięki temu kupno jest zawsze wcześniej niż sprzedaż. W pierwszym dniu cena - INT_MAX to wielka liczba ujemna, więc zysk się nie zmienia.

Schemat: najlepsza para „wcześniej — później” Gdy zadanie każe wybrać dwa elementy, i < j, i coś między nimi zmaksymalizować (zysk, różnicę, sumę), przejdź po j i trzymaj rekord najlepszego i spośród dotychczasowych. Pętla w pętli (około n·n kroków) zamienia się w jedną pętlę (n kroków) — dla 100 000 dni to różnica między 10 miliardami a 100 tysiącami operacji.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
vector<int> v = {2, 1, 4, 3};
int r = INT_MIN;
for (auto x : v) {
    r = max(r, x);
    cout << r;
}
Pokaż odpowiedź
2244Rekord do tej pory: 2, nadal 2, potem 4, nadal 4.
Ile razy rekord został pobity?
vector<int> v = {5, 5, 6, 1, 7};
int r = INT_MIN, ile = 0;
for (auto x : v) {
    if (x > r) ile++;
    r = max(r, x);
}
cout << ile;
Pokaż odpowiedź
3Rekord padał przy 5, 6 i 7. Druga piątka go tylko wyrównała.
Co wypisze ten fragment?
vector<int> a = {1, 3, 2};
vector<int> sm(3);
sm[2] = a[2];
for (int i = 1; i >= 0; i--) sm[i] = max(sm[i + 1], a[i]);
cout << sm[0] << sm[1] << sm[2];
Pokaż odpowiedź
332Od prawej: sm[2] = 2, sm[1] = max(2, 3) = 3, sm[0] = max(3, 1) = 3.
Ile budynków widać z prawej?
vector<int> h = {3, 1, 2};
int mp = INT_MIN, w = 0;
for (int i = 2; i >= 0; i--) {
    if (h[i] > mp) w++;
    mp = max(mp, h[i]);
}
cout << w;
Pokaż odpowiedź
2Widać 2 (najbliżej) i 3. Jedynkę zasłania dwójka.
Jaki jest najlepszy zysk?
vector<int> c = {5, 3, 8, 1, 4};
int mini = INT_MAX, z = 0;
for (auto x : c) {
    z = max(z, x - mini);
    mini = min(mini, x);
}
cout << z;
Pokaż odpowiedź
5Kupno po 3, sprzedaż po 8. Późniejsza jedynka daje tylko 4 − 1 = 3.
Jaki jest najlepszy zysk?
vector<int> c = {9, 4, 2};
int mini = INT_MAX, z = 0;
for (auto x : c) {
    z = max(z, x - mini);
    mini = min(mini, x);
}
cout << z;
Pokaż odpowiedź
0Ceny tylko spadają — najlepiej nic nie kupować.
Co wypisze ten fragment?
vector<int> a = {4, 8, 1, 2};
vector<int> pm(4);
pm[0] = a[0];
for (int i = 1; i < 4; i++) pm[i] = max(pm[i - 1], a[i]);
cout << pm[3];
Pokaż odpowiedź
8Ostatni element pm to maksimum całego ciągu.
Co wypisze ten fragment?
vector<int> v = {6, 7, 3, 5};
int r = INT_MAX;
for (auto x : v) {
    r = min(r, x);
    cout << r;
}
Pokaż odpowiedź
6633Minimum na bieżąco: 6, nadal 6, potem 3 i nadal 3.
Ćwiczenia · teraz Ty

7 ćwiczeń do tej części

0 / 7 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Najdłuższa seria, najlepsze okno i największa suma fragmentu

Ostatnia część lekcji to rekordy wśród fragmentów — kawałków ciągu złożonych z sąsiednich liczb. Najdłuższa seria wygranych, najcieplejsze trzy dni z rzędu, najlepszy kawałek drogi. We wszystkich tych zadaniach działa ten sam pomysł: idziemy po ciągu, trzymamy coś, co opisuje fragment kończący się w bieżącym miejscu, i robimy z tego rekord. Na koniec zobaczysz, jak szukać maksimów i minimów w tabeli dwuwymiarowej.

Najdłuższa seria: obecny i najlepszy

Seria to fragment, w którym wszystkie liczby są takie same. Trzymamy dwie zmienne: obecny — długość serii, w której właśnie jesteśmy, i najlepszy — rekord. Jeśli liczba jest taka sama jak poprzednia, seria trwa (obecny++). Jeśli inna — zaczyna się nowa seria o długości 1. Po każdym kroku poprawiamy rekord.

seria.cpp
vector<int> v = {7, 7, 2, 2, 2, 5, 2, 2};
int obecny = 1, najlepszy = 1;
for (int i = 1; i < (int)v.size(); i++) {
    if (v[i] == v[i - 1]) obecny++;
    else obecny = 1;
    najlepszy = max(najlepszy, obecny);   // w KAŻDYM kroku
}
cout << najlepszy << "\n";
▶ Wyjście
3
Serie: 7 7 (długość 2), 2 2 2 (długość 3), 5 (1) i 2 2 (2). Najdłuższa jest zielona — dwójki z pudełek 2–4. Dwójki z końca to już inna seria, bo przerwała je piątka.
Rekord w każdym kroku, nie tylko przy przerwaniu Kusi, żeby poprawiać rekord tylko wtedy, gdy seria się urywa. Ale ostatnia seria nigdy się nie urywa — kończą się dane. Jeśli najdłuższa seria jest na samym końcu, taki program jej nie zauważy. Aktualizuj rekord po każdej liczbie albo jeszcze raz po pętli.

Najdłuższy rosnący fragment

Ten sam schemat, inny warunek: fragment trwa, dopóki każda liczba jest większa od poprzedniej. Gdy liczba nie jest większa, rosnący fragment się urywa, a ona sama zaczyna nowy. Tym razem liczby wczytujemy bez vectora — wystarczy pamiętać poprzednią.

Najdłuższy rosnący fragment — animacja
Animacja działa po włączeniu JavaScriptu.
rosnacy.cpp
int n;
cin >> n;
int poprz;
cin >> poprz;
int obecny = 1, najlepszy = 1;
for (int i = 1; i < n; i++) {
    int x;
    cin >> x;
    if (x > poprz) obecny++;
    else obecny = 1;
    najlepszy = max(najlepszy, obecny);
    poprz = x;                // teraz x jest „poprzednią”
}
cout << najlepszy << "\n";
▶ Wejście
9 3 5 8 4 6 9 12 2 7
▶ Wyjście
4

Fragmenty rosnące: 3 5 8 (długość 3), 4 6 9 12 (długość 4) i 2 7 (długość 2). Najdłuższy ma 4.

Najważniejsza jest ostatnia linijka pętli: poprz = x. Bez niej program porównywałby każdą liczbę z pierwszą, a nie z poprzednią.

Najlepsze okno: k kolejnych liczb

Masz temperatury z n dni i chcesz znaleźć najcieplejsze k dni z rzędu — czyli k kolejnych liczb o największej sumie. Takie k kolejnych liczb to okno, które przesuwamy po danych o jedno miejsce. Liczenie sumy każdego okna od nowa to k dodawań na każde okno. Sprytniej: przy przesunięciu do okna wchodzi jedna liczba z prawej, a wychodzi jedna z lewej — więc suma zmienia się o t[i] - t[i - k].

Okna długości k = 3: 2+5+1 = 8, 5+1+8 = 14, 1+8+7 = 16, 8+7+3 = 18, 7+3+4 = 14. Najlepsze jest niebieskie: pudełka 3–5, suma 18.
okno.cpp
vector<int> t = {2, 5, 1, 8, 7, 3, 4};
int k = 3;
int suma = 0;
for (int i = 0; i < k; i++) suma += t[i];   // pierwsze okno
int najl = suma, start = 0;
for (int i = k; i < (int)t.size(); i++) {
    suma += t[i] - t[i - k];   // wchodzi t[i], wychodzi t[i - k]
    if (suma > najl) {
        najl = suma;
        start = i - k + 1;     // pierwsze pudełko nowego okna
    }
}
cout << najl << " od pozycji " << start + 1 << "\n";
▶ Wyjście
18 od pozycji 4

Gdy i = 3, do okna wchodzi t[3] = 8, a wychodzi t[0] = 2: suma 8 + 8 − 2 = 14. Tak, krok po kroku, dostajemy sumy wszystkich okien, wykonując w każdym kroku tylko dwa działania.

Okno kończy się w pudełku i, więc zaczyna w pudełku i - k + 1. Wypisujemy pozycję od 1, stąd + 1.

Największa suma fragmentu

A co, jeśli długość fragmentu jest dowolna? Liczby mogą być ujemne, więc nie opłaca się brać wszystkiego. Przykład: dla ciągu 2, −5, 3, 1, −2, 4, −6, 1 najlepszy kawałek to 3, 1, −2, 4 o sumie 6 — mimo że w środku jest −2. To zadanie ma piękne rozwiązanie w jednej pętli (w świecie programistów znane jako algorytm Kadane’a).

Pomysł: dla każdego miejsca i liczymy obecna — największą sumę fragmentu, który kończy się dokładnie w i. Taki fragment albo składa się z samej liczby x, albo jest najlepszym fragmentem kończącym się w i − 1 z doklejonym x. Wybieramy lepszą z tych dwóch możliwości: obecna = max(x, obecna + x). Innymi słowy: jeśli to, co mamy za sobą, ma sumę ujemną, lepiej to wyrzucić i zacząć od nowa. Wynikiem jest rekord wszystkich wartości obecna.

kadane.cpp
vector<long long> v = {2, -5, 3, 1, -2, 4, -6, 1};
long long obecna = v[0], najl = v[0];
for (int i = 1; i < (int)v.size(); i++) {
    obecna = max(v[i], obecna + v[i]);   // od nowa albo doklej
    najl = max(najl, obecna);
}
cout << najl << "\n";
▶ Wyjście
6
xmax(x, obecna + x)obecnanajl
2start22
−5max(−5, −3)−32
3max(3, 0) — od nowa33
1max(1, 4)44
−2max(−2, 2)24
4max(4, 6)66
−6max(−6, 0)06
1max(1, 1)16

Start od v[0], a nie od zera, ma znaczenie, gdy wszystkie liczby są ujemne. Fragment musi mieć co najmniej jedną liczbę, więc dla −4, −2, −7 odpowiedzią jest −2 (sama dwójka), a nie 0. Sumy mogą być duże, dlatego long long.

Maksima i minima w tabeli

W tabeli dwuwymiarowej (vector vectorów z lekcji o vectorze) rekord można liczyć dla każdego wiersza, dla każdej kolumny albo dla całości. Ciekawy przykład: trzy trasy rowerowe, każda ma cztery podjazdy o różnej trudności. Trudność trasy to jej najtrudniejszy podjazd — maksimum wiersza. Chcemy wybrać trasę, która jest najłatwiejsza, czyli taką, której najtrudniejszy podjazd jest jak najłatwiejszy — najmniejsze z maksimów.

Zielone pola to maksima wierszy: 8, 9 i 8. Najmniejsze z nich to 8 — trasa 0 (albo trasa 2, ta sama trudność).
tabela.cpp
vector<vector<int>> t = {
    {3, 8, 1, 6},
    {7, 2, 9, 4},
    {5, 5, 0, 8}};
int w = t.size(), k = t[0].size();
int najmZMaks = INT_MAX;
for (int i = 0; i < w; i++) {
    int m = *max_element(t[i].begin(), t[i].end());
    cout << "trasa " << i << ": " << m << "\n";
    najmZMaks = min(najmZMaks, m);
}
cout << "najlatwiejsza: " << najmZMaks << "\n";
for (int j = 0; j < k; j++) {          // maksimum każdej kolumny
    int m = t[0][j];
    for (int i = 1; i < w; i++) m = max(m, t[i][j]);
    cout << m << " ";
}
cout << "\n";
▶ Wyjście
trasa 0: 8 trasa 1: 9 trasa 2: 8 najlatwiejsza: 8 7 8 9 8

Dla wiersza wygodnie użyć max_element, bo wiersz t[i] to zwykły vector. Kolumna nie jest vectorem — jej liczby leżą w różnych wierszach — więc tu potrzebna jest pętla po wierszach z rekordem.

To schemat „najlepszy z najgorszych”: najpierw w każdej grupie szukasz najgorszego przypadku (max), a potem wybierasz grupę z najlepszym najgorszym przypadkiem (min).

Sprawdź się w głowie

Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Ile wynosi najdłuższa seria?
vector<int> v = {1, 1, 1, 2, 2};
int ob = 1, naj = 1;
for (int i = 1; i < 5; i++) {
    if (v[i] == v[i - 1]) ob++;
    else ob = 1;
    naj = max(naj, ob);
}
cout << naj;
Pokaż odpowiedź
3Trzy jedynki z rzędu.
Rekord poprawiany tylko przy przerwaniu. Co wypisze program?
vector<int> v = {4, 5, 5, 5, 5};
int ob = 1, naj = 1;
for (int i = 1; i < 5; i++) {
    if (v[i] == v[i - 1]) ob++;
    else { naj = max(naj, ob); ob = 1; }
}
cout << naj;
Pokaż odpowiedź
1Seria czterech piątek jest na końcu i nigdy się nie przerywa, więc nie trafia do rekordu. Poprawnie: 4.
Ile wynosi najdłuższy rosnący fragment?
vector<int> v = {1, 2, 2, 3, 4};
int ob = 1, naj = 1;
for (int i = 1; i < 5; i++) {
    if (v[i] > v[i - 1]) ob++;
    else ob = 1;
    naj = max(naj, ob);
}
cout << naj;
Pokaż odpowiedź
32 nie jest większe od 2, więc fragment się urywa. Najdłuższy to 2 3 4.
Jaka jest największa suma okna długości 2?
vector<int> t = {4, 1, 3, 5};
int s = t[0] + t[1], b = s;
for (int i = 2; i < 4; i++) {
    s += t[i] - t[i - 2];
    b = max(b, s);
}
cout << b;
Pokaż odpowiedź
8Sumy okien: 5, 4, 8.
Co wypisze ten fragment?
vector<int> v = {-2, 3, -1, 2};
int ob = v[0], naj = v[0];
for (int i = 1; i < 4; i++) {
    ob = max(v[i], ob + v[i]);
    naj = max(naj, ob);
}
cout << naj;
Pokaż odpowiedź
4Najlepszy fragment to 3, −1, 2 o sumie 4.
Co wypisze ten fragment?
vector<int> v = {-4, -2, -7};
int ob = v[0], naj = v[0];
for (int i = 1; i < 3; i++) {
    ob = max(v[i], ob + v[i]);
    naj = max(naj, ob);
}
cout << naj;
Pokaż odpowiedź
-2Same liczby ujemne — najlepszy fragment to jedna liczba, najbliższa zera.
Co wypisze ten fragment?
vector<vector<int>> t = {{2, 9}, {6, 5}};
int r = INT_MAX;
for (auto w : t) r = min(r, max(w[0], w[1]));
cout << r;
Pokaż odpowiedź
6Maksima wierszy: 9 i 6. Najmniejsze z nich to 6.
Co wypisze ten fragment?
vector<int> v = {1, -3, 2};
int ob = 0;
for (auto x : v) {
    ob = max(x, ob + x);
    cout << ob << " ";
}
Pokaż odpowiedź
1 -2 2max(1, 1) = 1, max(−3, −2) = −2, max(2, 0) = 2.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

9.1 Najdłuższa seriałatwe✓ zaliczone Najdłuższy kawałek ciągu złożony z takich samych sąsiednich liczb. obecny i najlepszyrekord w każdym kroku Rozwiąż 9.2 Seria wygranychłatwe✓ zaliczone Napis z literami W, R i P — ile najwięcej meczów z rzędu wygrała drużyna? seria w napisieobecny = 0 przy przerwaniustring Rozwiąż 9.3 Najdłuższy rosnący fragmentłatwe✓ zaliczone Najdłuższy kawałek ciągu, w którym każda liczba jest większa od poprzedniej. poprzednia liczbaobecny i najlepszy Rozwiąż 9.4 Maksima wierszy, minima kolumnłatwe✓ zaliczone Tabela liczb: największa w każdym wierszu i najmniejsza w każdej kolumnie. vector 2D*max_element(t[i]...)rekord w kolumnie Rozwiąż 9.5 Najcieplejsze k dniśrednie✓ zaliczone Okno k kolejnych dni o największej sumie temperatur — i gdzie się zaczyna. okno przesuwanesuma += t[i] − t[i − k]pierwsze najlepsze Rozwiąż 9.6 Największa suma fragmentuśrednie✓ zaliczone Kawałek ciągu o największej sumie — algorytm Kadane’a w jednej pętli. obecna = max(x, obecna + x)long longstart od pierwszej liczby Rozwiąż 9.7 Najłatwiejsza trasaśrednie✓ zaliczone Trudność trasy to jej najtrudniejszy podjazd. Która trasa jest najłatwiejsza? najlepszy z najgorszychmax w wierszu, min z maksimównumer wiersza Rozwiąż 9.8 Najstabilniejszy okresśrednie✓ zaliczone k kolejnych dni, w których temperatura najmniej się wahała. max_element i min_element na kawałkurekord różnicokno Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Baza zadań: max i min w praktyce

Znasz już wszystkie narzędzia: max i min dla dwóch liczb i dla listy w klamrach, zasadę jednego typu, rekord w pętli z dobrym startem, pozycję rekordu i remisy, liczenie wystąpień, max_element i min_element, przycinanie i wspólne części przedziałów, dwie i trzy największe liczby, rekordy na bieżąco od lewej i od prawej, najlepszy zysk, serie, okna i największą sumę fragmentu. Czas na zadania, które łączą kilka z tych rzeczy naraz. Są ułożone od najłatwiejszego do najtrudniejszego: najpierw rozgrzewka z jednym pomysłem, potem zadania średnie, w których łączysz dwa, trzy pomysły, a na końcu trudne — z wielkim finałem.

Przy każdym zadaniu widać, jakich zagadnień używa — także tych z poprzednich lekcji, jak napisy, pary, vector czy sortowanie. Jeśli coś brzmi obco, wróć do odpowiedniej części — mapa lekcji jest na górze strony. A tu masz najważniejsze schematy z lekcji w jednym miejscu:

Ściąga: gotowe schematy

Dwie i więcej liczb

max(a, b)   min(a, b)
max({a, b, c, d})
a + b + c - mx - mn  // środkowa
max(x, 0LL)          // long long!

Oba argumenty tego samego typu: 3.0, 7LL, (int)s.size().

Rekord w pętli

int maks = pierwsza;   // albo INT_MIN
for (...) maks = max(maks, x);
int mini = INT_MAX;
for (...) mini = min(mini, x);

Nigdy od 0, gdy liczby mogą być ujemne. Rekord „tylko z niektórych” — z flagą bool jest.

Gdzie i ile razy

if (x > maks) { maks = x; poz = i; }
// >  pierwsze,  >= ostatnie
if (x > maks) { maks = x; ile = 1; }
else if (x == maks) ile++;

Kto ma rekord — zapamiętaj imię albo numer obok wartości.

Gotowce

*max_element(v.begin(), v.end())
max_element(...) - v.begin()  // numer
max_element(t, t + n) - t
auto [lo, hi] = minmax_element(...);

Pierwsze wystąpienie (hi z minmax — ostatnie). Reguła jak w sort: [](a, b) { return … < …; }.

Granice

max(0, x)               // podłoga
min(limit, x)           // sufit
max(lo, min(hi, x))     // clamp(x, lo, hi)
max(0, min(b1, b2) - max(a1, a2))

Wspólna część: max początków, min końców.

Podium

if (x > m1) { m2 = m1; m1 = x; }
else if (x > m2) m2 = x;
// różne: else if (x < m1 && x > m2)
max(m1 * m2, s1 * s2)   // iloczyn

Najpierw przesuń w dół, potem wpisz na górę.

Na bieżąco

pm[i] = max(pm[i - 1], a[i]);
sm[i] = max(sm[i + 1], a[i]);
zysk = max(zysk, cena - mini);
mini = min(mini, cena);

Para „wcześniej — później”: jedna pętla z rekordem zamiast dwóch pętli.

Serie i fragmenty

ob = (warunek) ? ob + 1 : 1;
naj = max(naj, ob);        // co krok!
suma += t[i] - t[i - k];   // okno
ob = max(x, ob + x);       // Kadane

Sumy fragmentów bywają duże — long long.

Jak rozwiązywać zadania z max i min 1) Znajdź w treści słowo „naj…” i przetłumacz je: największy, najdłuższy, najlepszy → max; najmniejszy, najkrótszy, najtańszy, najszybszy → min. 2) Ustal, czego jest rekord: samej liczby, czegoś policzonego (długości, odległości, sumy), a może fragmentu? 3) Wybierz start: pierwsza liczba, INT_MIN / INT_MAX albo flaga. 4) Sprawdź, co z remisami i czy trzeba podać pozycję — wtedy if z ostrym albo nieostrym znakiem. 5) Gdy w pomyśle pojawia się pętla w pętli, a n jest duże, poszukaj rekordu „na bieżąco”. 6) Przetestuj skrajności: jedna liczba, wszystkie równe, wszystkie ujemne, ogromne wartości (long long!).
łatwe

Rozgrzewka · zadania 1–10

Jeden, dwa pomysły naraz: pogoda w maju, najszybszy biegacz, promocja 3 za 2, strata do lidera, fotoradar, najlepszy skok, dobowe wahania temperatury, ramka wokół punktów, bankomat i najdłuższa przerwa między autobusami.

1 Pogoda w majułatwe✓ zaliczone Najwyższa i najniższa temperatura miesiąca — i ile było najcieplejszych dni. max i minlicznik wystąpień rekordu Rozwiąż 2 Najszybszy biegaczłatwe✓ zaliczone Imiona i czasy biegu — kto wygrał? Najlepszy czas to najkrótszy! najlepszy czas = minrekord z imieniem Rozwiąż 3 Promocja 3 za 2łatwe✓ zaliczone Każdy klient kupuje trzy produkty i nie płaci za najtańszy. Ile zapłacili wszyscy? suma − min({…})long long Rozwiąż 4 Strata do liderałatwe✓ zaliczone Ile punktów brakuje każdemu zawodnikowi do lidera? dwa przejściamaks − xvector Rozwiąż 5 Fotoradarłatwe✓ zaliczone Najszybszy samochód, o ile przekroczył limit i ilu kierowców jechało za szybko. rekordmax(0, vmax − L)licznik Rozwiąż 6 Najlepszy skok konkursułatwe✓ zaliczone Każdy oddał trzy skoki. Jaki był najlepszy wynik konkursu i kto go uzyskał? max({a, b, c})rekord z numerem Rozwiąż 7 Dobowe wahaniałatwe✓ zaliczone Którego dnia różnica między najzimniejszą a najcieplejszą porą była największa? rekord różnicynumer dniaremis Rozwiąż 8 Ramka wokół punktówłatwe✓ zaliczone Najmniejszy prostokąt, w którym mieszczą się wszystkie punkty. Jakie ma pole? cztery rekordymin i max x oraz ylong long Rozwiąż 9 Bankomatłatwe✓ zaliczone Wypłata to najmniejsze z trzech: prośba, limit bankomatu i stan konta. min({…}) z trzech ograniczeńsymulacja Rozwiąż 10 Najdłuższa przerwa między autobusamiłatwe✓ zaliczone Godziny przyjazdów autobusów — jak długo najdłużej trzeba czekać i od kiedy? rekord różnic sąsiadówpozycja rekordu Rozwiąż
średnie

Średnie · zadania 11–20

Kilka sztuczek naraz: najdziwniejszy wynik, dwie kasy w sklepie, najcieplejszy dzień każdego tygodnia, najlepszy moment na transakcję, iloczyn trzech liczb, puchar, wspólne pole prostokątów, spotkanie w połowie drogi, pogoda na wycieczkę oraz najlepszy wiersz i kolumna.

11 Najdziwniejszy wynikśrednie✓ zaliczone Wynik najdalej od średniej — policzony bez ani jednego ułamka. abs(n · x − S)dwa przejścialong longremis Rozwiąż 12 Dwie kasyśrednie✓ zaliczone Każdy klient idzie do kasy, która zwolni się pierwsza. Kiedy skończy się obsługa? min — która kasa wolnamax — koniec pracylong long Rozwiąż 13 Najcieplejszy dzień każdego okresuśrednie✓ zaliczone Dla każdego okresu k kolejnych dni — najwyższa temperatura w tym okresie. okno k dnimax_element na kawałku Rozwiąż 14 Najlepszy moment na transakcjęśrednie✓ zaliczone Największy zysk z kupna i sprzedaży — oraz dni, w których to zrobić. najlepszy zyskpozycja minimumremisy Rozwiąż 15 Iloczyn trzech liczbśrednie✓ zaliczone Trzy liczby o największym iloczynie — dwie bardzo ujemne mogą zmienić wszystko. trzy największe i dwie najmniejszelong longmax dwóch kandydatów Rozwiąż 16 Pucharśrednie✓ zaliczone Turniej pucharowy, w którym zawsze wygrywa silniejszy. Kto zagra w finale? max_element na połówkachmyślenie zamiast symulacji Rozwiąż 17 Wspólne pole wielu prostokątówśrednie✓ zaliczone n prostokątów na planszy — jakie pole ma część wspólna wszystkich? cztery rekordymax(0LL, …)long long Rozwiąż 18 Spotkanie w połowie drogiśrednie✓ zaliczone Gdzie spotkać się, żeby osoba z najdalszą drogą miała jak najbliżej? max − minzaokrąglenie w góręmyślenie Rozwiąż 19 Pogoda na wycieczkęśrednie✓ zaliczone k dni wycieczki, których najzimniejszy dzień jest jak najcieplejszy. najlepszy z najgorszychmin w okniemax z minimów Rozwiąż 20 Najlepszy wiersz i najlepsza kolumnaśrednie✓ zaliczone Który wiersz i która kolumna tabeli mają największą sumę? sumy wierszy i kolumnrekord z numeremvector 2D Rozwiąż
trudne

Trudne · zadania 21–28

Deszczówka, dwie transakcje, naszyjnik z koralików, najdłuższa górka, największy iloczyn fragmentu, ścieżka po planszy, ławka w parku — a na koniec wielki finał: wyprawa w góry.

21 Deszczówkatrudne✓ zaliczone Słupki różnej wysokości, a po deszczu woda w dołkach. Ile jej się zebrało? tablice pm i smmin(pm[i], sm[i]) − h[i]long long Rozwiąż 22 Dwie transakcjetrudne✓ zaliczone Najwyżej dwie transakcje kupna i sprzedaży, jedna po drugiej. Jaki największy łączny zysk? najlepszy zysk od lewej i od prawejpodział w dniu itablice Rozwiąż 23 Naszyjnik z koralikówtrudne✓ zaliczone Największa suma fragmentu — ale koraliki są ułożone w kółko. Kadane dla max i dla minsuma całości − najgorszy fragmentlong long Rozwiąż 24 Najdłuższa górkatrudne✓ zaliczone Fragment, który najpierw ściśle rośnie, a potem ściśle maleje. Jak długi może być? rekordy z lewej i z prawejup[i] i down[i]max Rozwiąż 25 Największy iloczyn fragmentutrudne✓ zaliczone Kawałek ciągu o największym iloczynie — trzeba pilnować i maksimum, i minimum. największy i najmniejszy na bieżącominus razy minuslong long Rozwiąż 26 Ścieżka po planszytrudne✓ zaliczone Idziesz tylko w prawo albo w dół i zbierasz monety. Ile najwięcej uzbierasz? najlepszy wynik do każdego polamax(z góry, z lewej)vector 2D Rozwiąż 27 Ławka w parkutrudne✓ zaliczone Usiądź na wolnym miejscu jak najdalej od najbliższej osoby. najbliższy z lewej i z prawejmin z dwóch odległościmax po miejscach Rozwiąż 28 Wielki finał: wyprawa w górytrudne✓ zaliczone Pięć pytań o jeden szlak górski — i pięć schematów z tej lekcji naraz. rekordyskoki sąsiadównajdłuższa serianajlepszy zyskpobite rekordy Rozwiąż

Częste błędy i dobre praktyki

⚖️
Dwa różne typy
max(3, 2.5), max(x, 7) dla long long x i max(d, s.size()) się nie skompilują. Wyrównaj typy: 3.0, 7LL, (int)s.size().
🗑️
Wynik bez przypisania
max(a, b); w osobnej linijce niczego nie zmienia — wynik przepada. Pisz a = max(a, b); albo od razu go wypisz.
0️⃣
Rekord od zera
Przy samych liczbach ujemnych maks = 0 daje 0 — liczbę spoza danych. Zaczynaj od pierwszej liczby albo od INT_MIN / INT_MAX.
🧩
Brak klamer
Trzy liczby i więcej to max({a, b, c}). Bez klamer, w max(a, b, c), trzecie miejsce czeka na regułę porównania i kompilator zgłasza błąd.
🎯
> czy >=
Ostry znak zostawia pierwsze wystąpienie rekordu, nieostry — ostatnie. Przeczytaj w treści, które jest potrzebne, zanim napiszesz warunek.
🔁
Licznik bez zerowania
Licząc wystąpienia rekordu w jednej pętli, przy nowym rekordzie ustaw ile = 1. Inaczej licznik pamięta wyrównania starego, gorszego rekordu.
⭐
Gwiazdka przy max_element
max_element oddaje strzałkę. Wartość to *max_element(…), numer to max_element(…) - v.begin(). Na pustym vectorze gwiazdka czyta śmieci.
🧱
Odwrócone granice
Przycinanie to max(lo, min(hi, x)) albo clamp(x, lo, hi). Przy dolnej granicy stoi max, przy górnej min — zamienione dają zawsze tę samą liczbę.
🥈
Srebro nadpisane złotem
Przy nowym rekordzie najpierw m2 = m1, dopiero potem m1 = x. Odwrotna kolejność kopiuje nowe złoto na srebro.
🏁
Ostatnia seria
Rekord serii poprawiaj w każdym kroku, a nie tylko przy przerwaniu — ostatnia seria nigdy się nie przerywa i bez tego przepada.
⏱️
Pętla w pętli przy dużym n
Szukanie maksimum osobno dla każdego miejsca to około n·n kroków. Rekord „na bieżąco” (pm, sm, najniższa cena do tej pory) robi to samo w jednej pętli.
💥
Za mały typ
Iloczyn dwóch liczb rzędu miliarda, suma fragmentu albo pole prostokąta nie mieszczą się w int. Używaj long long — razem z LLONG_MIN, LLONG_MAX i 0LL.

Co dalej?

max i min będą w Twoich programach już zawsze — w rekordach, granicach, przedziałach i w niemal każdym zadaniu, w którym pada słowo „naj…”. Rekord liczony „na bieżąco” wróci w programowaniu dynamicznym, a szukanie najlepszego fragmentu — w zadaniach olimpijskich na każdym poziomie. Następna lekcja to kolejne narzędzie matematyczne: zaokrąglanie liczb w górę, w dół i do najbliższej całości. A jeśli chcesz trenować z mentorami — dołącz do T-Olimpians.