Parcurgerea unui vector

De ce contează?

Profesorul vrea suma notelor clasei și cea mai mare notă. Nu face două liste — trece o dată prin catalog, ține în minte „totalul de până acum" și „cel mai mare văzut". Exact asta înseamnă parcurgerea unui vector: o trecere, mai multe informații culese simultan.

Cum parcurgem un vector

Parcurgerea înseamnă să vizităm fiecare element exact o dată, de la stânga la dreapta (index 0 → n-1), acumulând informații pe parcurs.

Tiparul de bază:

pentru i de la 0 la n-1:
    prelucreaza v[i]

Algoritmul — sumă și maxim

suma  ← 0
maxim ← v[0]

pentru i de la 0 la n-1:
    suma ← suma + v[i]
    daca v[i] > maxim:
        maxim ← v[i]

Urmărire pe v = {4, 7, 2, 9, 3}:

i	v[i]	sumă	maxim
—	—	0	4
0	4	4	4
1	7	11	7
2	2	13	7
3	9	22	9
4	3	25	9

Rezultat: sumă = 25, maxim = 9.

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int v[1001];
    for (int i = 0; i < n; i++) cin >> v[i];

    int suma = 0;
    int maxim = v[0];
    for (int i = 0; i < n; i++) {
        suma += v[i];
        if (v[i] > maxim) maxim = v[i];
    }

    cout << "Suma: " << suma << "\n";
    cout << "Maxim: " << maxim << "\n";
    return 0;
}

Complexitate

Operație	Timp	Spațiu suplimentar
Sumă + maxim	O(n)	O(1)

Observația-cheie

Poți calcula oricâte proprietăți într-o singură parcurgere: sumă, maxim, minim, număr de pare, produs parțial. Nu parcurgi vectorul de k ori pentru k proprietăți — o singură trecere e suficientă.

Vizualizare

Urmărește cum se actualizează suma și maximul la fiecare pas:

Indiciu

Folosește ← și → pentru a avansa pas cu pas, sau Redă pentru animație automată.

Greșeli frecvente

Greșeala 1: maxim = 0 când vectorul poate conține valori negative — vei returna 0 în loc de maximul real. Inițializează mereu cu v[0].

Greșeala 2: Pornești bucla de la i = 1 dar inițializezi maxim = v[0] — pentru maxim e corect, însă v[0] nu se mai adaugă la sumă.

Greșeala 3: suma = v[i] în loc de suma += v[i] — suprascrii suma la fiecare pas în loc să acumulezi.

Recapitulare

Parcurgerea vizitează fiecare element o singură dată, de la 0 la n-1.
Suma pornește de la 0; maximul pornește de la v[0].
O singură parcurgere O(n) poate calcula simultan mai multe proprietăți.