De ce contează?
Soldul contului tău bancar nu e suma tuturor tranzacțiilor stocate — banca ține un singur număr curent și îl actualizează la fiecare tranzacție. Tu faci la fel: citești numerele pe rând și actualizezi ce ai nevoie, fără să ții minte toată lista.
Ideea centrală
Multe prelucrări se pot face „din zbor" — citești un număr, îl procesezi imediat, apoi îl uiți. Nu ai nevoie de niciun vector care să stocheze toată secvența.
Ce poți calcula fără vector:
- Suma, produsul
- Maximul, minimul
- Numărul de elemente cu o proprietate
- Media aritmetică (sumă + contor)
Ce necesită stocarea tuturor valorilor:
- Mediana (necesită sortare — nu poți sorta fără toate valorile)
- Al k-lea element în ordine crescătoare
- Operații care compară elemente non-adiacente sau revin la valori anterioare
Pattern-ul de bază
Variabila x citește câte un element pe rând. Imediat după citire o procesezi — și la iterația următoare valoarea ei e suprascrisă. Nici nu ai unde stoca mai mult.
// Citim n numere si calculam suma si maximul simultan
int n; cin >> n;
long long suma = 0;
int maxim = INT_MIN; // sau citim primul element separat
for (int i = 0; i < n; i++) {
int x;
cin >> x; // citim valoarea
suma += x; // procesam imediat
if (x > maxim) maxim = x;
// x nu mai e necesar — urmatoarea iteratie il suprascrie
}Implementare C++ — mai multe calcule simultan
#include <iostream>
#include <climits>
#include <fstream>
using namespace std;
int main() {
ifstream fin("date.in");
ofstream fout("date.out");
int n;
fin >> n;
long long suma = 0;
int maxim = INT_MIN, minim = INT_MAX;
int nr_pare = 0;
for (int i = 0; i < n; i++) {
int x;
fin >> x;
suma += x;
if (x > maxim) maxim = x;
if (x < minim) minim = x;
if (x % 2 == 0) nr_pare++;
}
fout << "Suma: " << suma << "\n";
fout << "Max: " << maxim << ", Min: " << minim << "\n";
fout << "Pare: " << nr_pare << "\n";
return 0;
}O singură parcurgere, O(1) memorie suplimentară — calculăm 4 lucruri simultan.
Aceasta e abordarea standard la olimpiade pentru secvențe mari de intrare. Dacă problema nu cere să „revii" la valori anterioare sau să le reordonezi, aproape sigur poți procesa fără vector — economisești memorie și simplifici codul.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Orice calcul streaming | O(n) | O(1) |
| Cu vector | O(n) | O(n) |
Vizualizare
Urmărește cum suma și maximul se calculează din mers, fără să stochezi vectorul:
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: Declari int x în afara buclei din reflex. Nu e greșit, dar nu e necesar — variabila se poate declara în interiorul buclei (int x; cin >> x;).
Greșeala 2: Inițializezi maxim = 0. Dacă toate valorile sunt negative, maximul rămâne 0 — incorect. Folosește INT_MIN (din <climits>) sau citește primul element separat ca valoare inițială.
Greșeala 3: Crezi că „fără vector" e mereu mai bun. Dacă problema cere să afișezi elementele sortate sau să faci căutare, vei avea nevoie de vector. Alege în funcție de ce cere problema.