Maxime, minime și pozițiile lor în C++

Pentru a găsi cea mai mare valoare dintr-o listă, poți păstra cel mai bun rezultat întâlnit până în acel moment. Fiecare număr nou este comparat cu acest rezultat și îl înlocuiește doar dacă este mai mare. Pentru minimum, comparația se inversează.

Lecția continuă ideea de prelucrare pe rând din sume și numărări. Vei învăța să inițializezi corect extremele, să numeri aparițiile maximului și să alegi prima poziție când există egalități.

Pornește de la o valoare care există în listă

Citim n, cu 1 <= n <= 100000, apoi n numere între -1000000000 și 1000000000. Prima valoare este, provizoriu, atât minimum, cât și maximum.

#include <iostream>

int main() {
    int n = 0;
    long long x = 0;
    std::cin >> n >> x;
    long long minim = x, maxim = x;
    int aparitiiMaxim = 1;
    for (int i = 1; i < n; ++i) {
        std::cin >> x;
        if (x < minim) {
            minim = x;
        }
        if (x > maxim) {
            maxim = x;
            aparitiiMaxim = 1;
        } else if (x == maxim) {
            ++aparitiiMaxim;
        }
    }
    std::cout << minim << ' ' << maxim << ' ' << aparitiiMaxim << '\n';
    return 0;
}

Pentru 5 valori, -4 -9 -4 -2 -2, se afișează -9 -2 2. Observă că toate valorile sunt negative. Dacă inițializai maximul cu zero, ai fi obținut o valoare care nici măcar nu apare în listă.

Prima citire este făcută înaintea buclei. De aceea mai rămân exact n - 1 valori de citit. La n = 1, bucla nu se execută, minimum și maximum sunt valoarea citită, iar numărul aparițiilor este unu.

De ce resetăm numărul aparițiilor

Când apare un maximum nou, aparițiile vechiului maximum nu mai contează. Contorul devine 1, pentru numărul tocmai citit. Când apare aceeași valoare ca maximul curent, contorul crește.

Urmărește lista 3 3 5 5 2: după primele două valori, maximul este 3 cu două apariții. La 5, maximul se schimbă și contorul revine la 1. Următorul 5 îl aduce la 2. Valoarea 2 nu schimbă maximul sau contorul lui.

Verificarea minimului este independentă de verificarea maximului. După fiecare citire, cele două variabile descriu extremele numerelor deja prelucrate.

Când găsim un maxim nou, numărăm aparițiile lui de la unu.

Poziția primei apariții a maximului

Pozițiile din exemplul următor sunt numerotate de la 1. Păstrăm prima apariție atunci când valoarea maximă se repetă.

#include <iostream>

int main() {
    int n = 0;
    long long maxim = 0;
    std::cin >> n >> maxim;
    int pozitie = 1;
    for (int i = 2; i <= n; ++i) {
        long long x = 0;
        std::cin >> x;
        if (x > maxim) {
            maxim = x;
            pozitie = i;
        }
    }
    std::cout << maxim << ' ' << pozitie << '\n';
    return 0;
}

Pentru 4 valori, 8 3 8 1, rezultatul este 8 1. Folosim strict >: o valoare egală nu înlocuiește poziția salvată. Dacă ai folosi >=, ai păstra ultima apariție, deci rezultatul ar fi 8 3.

Cazuri de margine și cost

Testează o singură valoare, valori toate egale, valori toate negative și maximum aflat la început sau la sfârșit. Dacă enunțul permite o listă goală, trebuie să stabilească și rezultatul pentru ea; programele de aici cer explicit n >= 1.

Nu ai nevoie să sortezi lista. O singură parcurgere găsește extremele în timp O(n) și memorie suplimentară O(1). Sortarea ar rezolva o problemă mai generală decât cea cerută.

Exersează

1. Ce afișează primul program pentru 3 valori egale cu 7?
2. Schimbă al doilea program pentru ultima poziție a maximului.
3. Găsește prima poziție a minimului.
4. De ce nu este suficient să alegi mereu minim = 0?

Răspunsuri: 7 7 3; schimbi comparația în >=; păstrezi prima valoare și actualizezi la <; dacă toate valorile sunt pozitive, zero nu este minimul listei și nici nu aparține listei.

Următoarea lecție prelucrează cifrele unui număr, fără să memoreze o listă de cifre.

Întrebări frecvente

De ce nu inițializez maximul cu zero?

Dacă toate valorile sunt negative, zero ar rămâne un maxim care nici nu apare în date. Pentru un șir nevid poți începe cu primul element.

Cum păstrez prima poziție a maximului?

Actualizezi poziția numai când găsești o valoare strict mai mare. La egalitate păstrezi poziția deja memorată, care este prima.

Cum păstrez ultima poziție a maximului?

Actualizezi și la egalitate, folosind regula potrivită. Fiecare nouă apariție înlocuiește poziția anterioară, iar la final rămâne ultima.

Cum număr aparițiile maximului?

La un maxim nou resetezi numărul aparițiilor la unu. La o valoare egală cu maximul curent crești contorul; la valori mai mici nu îl modifici.

Există maxim pentru un șir gol?

Nu există un element maxim al unui șir gol în sensul obișnuit. Cerința trebuie să excludă acest caz sau să definească un rezultat special.