De ce contează?
La olimpiadele sportive se acordă aur și argint. Ca să găsești câștigătorul de argint, nu sortezi toți participanții — ții „campionul curent" și „cel mai bun clasat după el". La fiecare nou concurent actualizezi cu grijă ambele, în ordinea corectă.
Algoritmul
Menținem max1 (cel mai mare) și max2 (al doilea). Patru cazuri la fiecare element nou x:
x > max1→xe noul maxim absolut. Vechiulmax1coboară înmax2.x == max1→ depinde dacă vrem duplicate (vezi mai jos).max2 < x < max1→xe noulmax2.x <= max2→ nimic de actualizat.
| sir | 3 | 7 | 5 | 2 | 9 | 4 |
| index | 0 | 1 | 2 | 3 | 4 | 5 |
max2 | max1 |
Sir: 3, 7, 5, 2, 9, 4
max1=INT_MIN, max2=INT_MIN
x=3: 3>INT_MIN → max2=INT_MIN, max1=3
x=7: 7>3 → max2=3, max1=7
x=5: 5<7, 5>3 → max2=5, max1=7
x=2: 2<5 → nimic
x=9: 9>7 → max2=7, max1=9
x=4: 4<9, 4<7 → nimic
Rezultat: max1=9, max2=7Implementare C++ — valori distincte
#include <iostream>
#include <climits>
#include <fstream>
using namespace std;
int main() {
ifstream fin("maxime.in");
ofstream fout("maxime.out");
int n;
fin >> n;
int max1 = INT_MIN, max2 = INT_MIN;
for (int i = 0; i < n; i++) {
int x;
fin >> x;
if (x > max1) {
max2 = max1; // vechiul max1 coboara
max1 = x;
} else if (x > max2) {
max2 = x; // actualizeaza doar max2
}
}
fout << max1 << " " << max2 << "\n";
return 0;
}Exemplu: 6 / 3 7 5 2 9 4 → 9 7
Varianta cu duplicate permise
Dacă 7, 7 sunt două valori diferite (din poziții diferite) și vrei max1=7, max2=7:
if (x >= max1) { // >= in loc de >
max2 = max1;
max1 = x;
} else if (x > max2) {
max2 = x;
}Extinderea la top-3 urmează același tipar: verifici de la max1 în jos și actualizezi primul slot mai mic decât x. Pentru k mare însă, un vector sortat (sau un heap) e mult mai practic decât k variabile separate.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Primele două maxime | O(n) | O(1) |
Vizualizare
Urmărește scanarea care găsește maximul — același principiu, pe care îl extinzi la al doilea maxim:
Folosește ← și → pentru a avansa pas cu pas, sau Redă pentru animație automată. Apasă Laborator ca să testezi cu propriul tău șir.
Greșeala 1: Scrii max1 = x; max2 = max1; — suprascrii max1 înainte să-l salvezi în max2. Vechea valoare a lui max1 se pierde. Ordinea corectă: max2 = max1; max1 = x;.
Greșeala 2: Uiți ramura else if (x > max2). Fără ea, un element mai mic decât max1 dar mai mare decât max2 nu actualizează nimic.
Greșeala 3: Inițializezi max2 = max1 = 0. Dacă toate valorile sunt negative, obții max1=0 și max2=0 — ambele greșite. Inițializează cu INT_MIN.