Invatare Atomica

Secvente in vectori

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei invata sa lucrezi cu subsecvente (portiuni consecutive) ale unui vector, sa calculezi sume pe intervale eficient cu sume partiale, sa gasesti secventa de suma maxima si sa aplici aceste tehnici la subiecte de tip Bacalaureat si concurs.

Dupa aceasta lectie vei putea:

  • Sa definesti o subsecventa si sa o distingi de un subsir
  • Sa construiesti vectorul de sume partiale si sa calculezi suma pe orice interval in O(1)
  • Sa determini cea mai lunga secventa cu o proprietate data (crescatoare, constanta, etc.) in O(n)
  • Sa gasesti secventa de suma maxima dintr-un vector cu numere negative (algoritm Kadane, O(n))
  • Sa numarezi subsecvente cu suma data si sa rezolvi probleme tip Bacalaureat

Incearca singur!

Provocare initiala:

Fie vectorul v = [3, -1, 4, -1, 5, -9, 2, 6]. Gaseste prin inspectie vizuala subsecventa formata din elemente consecutive a carei suma este maxima. Noteaza indicii de inceput si sfarsit.

💡 Ai nevoie de un indiciu?

O subsecventa inseamna elemente consecutive din vector (nu poti sari peste elemente). Calculeaza suma pentru cateva portiuni: v[0..4] = 3-1+4-1+5 = 10. Este aceasta maxima?

Vei invata in aceasta lectie algoritmul Kadane care gaseste raspunsul optim in O(n)!

1

1. Subsecventa vs. subsir

O subsecventa (sau secventa) a vectorului v[0..n-1] este portiunea v[l..r] formata din elemente consecutive: v[l], v[l+1], ..., v[r], unde 0 ≤ l ≤ r ≤ n-1.
Lungimea subsecventei v[l..r] este r − l + 1.
Terminologie exacta:
  • Subsecventa = portiune continua, fara salturi (contiguous subarray in engleza)
  • Subsir = elemente extrase in ordine, dar nu neaparat consecutive (pot fi salturi)
Exemplu concret cu v = [3, 1, 4, 1, 5, 9, 2, 6]:
  • v[2..5] = [4, 1, 5, 9] → subsecventa de lungime 4, suma = 19
  • v[0..7] → intregul vector, suma = 31
  • [3, 4, 5] → NU este subsecventa (sare indicii 1 si 3)
  • v[5..5] = [9] → subsecventa de lungime 1 (un singur element)
2

2. Sume partiale (prefix sums) — interogare O(1)

Vectorul de sume partiale sp are n+1 elemente:
sp[0] = 0    sp[i] = sp[i-1] + v[i-1] pentru i = 1..n
Formula cheie: suma subsecventei v[l..r] = sp[r+1] − sp[l] in O(1). 
# Sume partiale pentru vectorul v
v = [3, 1, 4, 1, 5, 9, 2, 6]
n = len(v)

# Construire O(n): sp[0]=0, sp[i]=sp[i-1]+v[i-1]
sp = [0] * (n + 1)
for i in range(n):
    sp[i+1] = sp[i] + v[i]

print("Vector v:      ", v)
print("Sume partiale: ", sp)

# Interogare O(1): suma v[l..r] = sp[r+1] - sp[l]
l, r = 2, 5
suma_lr = sp[r+1] - sp[l]
print(f"suma({l},{r}) = sp[{r+1}] - sp[{l}] = {sp[r+1]} - {sp[l]} = {suma_lr}")
Output real (rulat cu python):
Vector v:       [3, 1, 4, 1, 5, 9, 2, 6]
Sume partiale:  [0, 3, 4, 8, 9, 14, 23, 25, 31]
suma(2,5) = sp[6] - sp[2] = 23 - 4 = 19
De ce este eficient?
  • Fara sume partiale: suma(l,r) costa O(r−l+1). Cu Q interogari: O(n·Q) total.
  • Cu sume partiale: preprocesare O(n), fiecare interogare O(1). Cu Q interogari: O(n+Q) total.
  • La n=100.000 si Q=50.000: diferenta intre 5 miliarde vs 150.000 operatii.
3

3. Cea mai lunga secventa cu proprietate data — O(n)

Tehnica generala (O(n), O(1) memorie): parcurgem vectorul mentinand lung_cur (lungimea secventei curente) si lung_max (maximul gasit). La fiecare pas: daca proprietatea continua, incrementam; daca nu, resetam la 1. 
# Cea mai lunga secventa strict crescatoare consecutiva
v = [2, 4, 6, 3, 5, 1, 7, 8, 9]
n = len(v)

lung_max = 1
lung_cur = 1
end_m = 0   # indicele de sfarsit al secventei maxime

for i in range(1, n):
    if v[i] > v[i-1]:          # proprietatea: strict crescator
        lung_cur += 1
    else:
        lung_cur = 1           # rupe secventa: resetam
    if lung_cur > lung_max:
        lung_max = lung_cur
        end_m = i

start_m = end_m - lung_max + 1
print("Vector:", v)
print(f"Secventa strict crescatoare: v[{start_m}..{end_m}] = {v[start_m:end_m+1]}")
print(f"Lungime: {lung_max}")
Output real (rulat cu python):
Vector: [2, 4, 6, 3, 5, 1, 7, 8, 9]
Secventa strict crescatoare: v[5..8] = [1, 7, 8, 9]
Lungime: 4
Adaptare pentru alte proprietati — schimba doar conditia if:
  • Secventa de elemente egale: if v[i] == v[i-1]
  • Secventa nedescrescatoare: if v[i] ≥ v[i-1]
  • Secventa de elemente pare: if v[i] % 2 == 0 (si initializeaza lung_cur = 1 if v[0]%2==0 else 0)
4

4. Secventa de suma maxima — Algoritmul Kadane O(n)

Problema: gaseste subsecventa v[l..r] cu suma maxima (vectorul poate contine si numere negative).
Algoritmul Kadane: la fiecare pozitie i, decidem daca extindem secventa curenta sau incepem una noua. Regula: daca suma_cur < 0, ea numai scade suma viitoare, deci incepem de la v[i]. 
# Kadane: secventa de suma maxima O(n)
v = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
n = len(v)

suma_max = v[0]   # initializare cu v[0], nu cu 0!
suma_cur = v[0]
s = 0; e = 0; ts = 0   # start/end al secventei maxime; ts = temp_start

for i in range(1, n):
    if suma_cur + v[i] < v[i]:   # echivalent: suma_cur < 0
        suma_cur = v[i]           # incepem secventa noua de la i
        ts = i
    else:
        suma_cur = suma_cur + v[i]  # extindem secventa curenta
    if suma_cur > suma_max:
        suma_max = suma_cur
        s = ts; e = i

print("Vector:", v)
print(f"Suma maxima = {suma_max}")
print(f"Secventa: v[{s}..{e}] = {v[s:e+1]}")
Output real (rulat cu python):
Vector: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Suma maxima = 6
Secventa: v[3..6] = [4, -1, 2, 1]
Urmarire pas cu pas (primele 5 iteratii):
iv[i]suma_cursuma_maxActiune
init-2-2-2start
1111-2+1<1 → restart de la i=1
2-3-211-3=-2, extinde (1≥0)
3444-2+4<4 → restart de la i=3
4-1344-1=3, extinde
Atentie: cazuri limita importante
  • Initializeaza suma_max = v[0], nu 0 (altfel dai gres cand toate elementele sunt negative)
  • Daca toate elementele sunt negative, Kadane returneaza corect maximul (cel mai putin negativ)
5

5. Sume partiale in C++ EXCLUSIV INTENSIV

⚡ Sectiune doar pentru intensiv informatica

Acelasi algoritm de sume partiale implementat in C++. Diferente fata de Python: declarare explicita de tip si dimensiune, initializare cu = {0} (seteaza TOATE elementele la 0), indexare identica.

#include <iostream>
using namespace std;
int main() {
    int v[] = {3, 1, 4, 1, 5, 9, 2, 6};
    int n = 8;
    int sp[9] = {0};  // initializeaza TOATE cele 9 elemente la 0
    for (int i = 0; i < n; i++)
        sp[i+1] = sp[i] + v[i];
    // Afisare sp
    cout << "sp = [";
    for (int i = 0; i <= n; i++) {
        if (i) cout << ", ";
        cout << sp[i];
    }
    cout << "]" << endl;
    // Interogare: suma v[2..5] in O(1)
    int l = 2, r = 5;
    cout << "suma(2,5) = sp[6] - sp[2] = "
         << sp[r+1] << " - " << sp[l]
         << " = " << (sp[r+1] - sp[l]) << endl;
    return 0;
}
Output real (compilat g++ -std=c++17, rulat):
sp = [0, 3, 4, 8, 9, 14, 23, 25, 31]
suma(2,5) = sp[6] - sp[2] = 23 - 4 = 19

Rezultatul este identic cu Python. Logica matematica a algoritmului nu depinde de limbaj — doar sintaxa difera.

6

6. Aplicatie: numararea subsecventelor cu suma data

Cu sume partiale putem testa eficient toate perechile (l, r) si numara subsecventele care satisfac o conditie de suma. Complexitate: O(n²) cu sume partiale (O(1) per pereche), fata de O(n³) fara. 
# Numara subsecventele cu suma egala cu target
v = [1, 2, 3, 4, 5]
n = len(v)
target = 5

# Construim sume partiale
sp = [0] * (n + 1)
for i in range(n):
    sp[i+1] = sp[i] + v[i]

contor = 0
for l in range(n):
    for r in range(l, n):
        if sp[r+1] - sp[l] == target:
            contor += 1
            print(f"  v[{l}..{r}] = {v[l:r+1]}, suma = {target}")

print(f"Total subsecvente cu suma {target}: {contor}")
Output real (rulat cu python):
  v[1..2] = [2, 3], suma = 5
  v[4..4] = [5], suma = 5
Total subsecvente cu suma 5: 2
Verificare manuala:
  • v[1..2] = [2, 3]: 2 + 3 = 5 ✓
  • v[4..4] = [5]: 5 = 5 ✓
  • v[0..1] = [1, 2] = 3 ≠ 5; v[0..2] = 6 ≠ 5; v[2..3] = 7 ≠ 5 etc.

Exercitii practice

Exercitiul 1 (Nivel minim) — Sume partiale pe hartie

Fie v = [5, 2, 8, 1, 3]. Construieste manual vectorul de sume partiale sp (6 elemente, incepand cu 0). Calculeaza suma elementelor din v[1..3] folosind formula sp[r+1] - sp[l].

Raspuns asteptat: sp = [0, 5, 7, 15, 16, 19]; suma(1,3) = sp[4] - sp[1] = 16 - 5 = 11.

Exercitiul 2 (Nivel standard) — Secventa descrescatoare

Scrie un program Python care gaseste cea mai lunga subsecventa strict descrescatoare consecutiva dintr-un vector dat. Afiseaza indicii de inceput si sfarsit si lungimea.

Testare: pentru v = [9, 7, 5, 8, 4, 2, 1, 3], raspunsul este v[2..6] = [5, 8, 4, 2, 1]? Verifica singur! (Indiciu: conditia trebuie sa fie v[i] < v[i-1].)

Exercitiul 3 (Nivel performanta) — Kadane complet cu cazuri limita

Modifica algoritmul Kadane pentru a trata corect: (a) toate elementele negative — returneaza maximul (cel mai putin negativ), nu 0; (b) vectorul are un singur element. Testeaza cu v = [-5, -3, -1, -4] (raspuns: suma_max = -1, secventa v[2..2]) si cu v = [7] (raspuns: suma_max = 7).

Ce ai invatat astazi

  • Definitia subsecventei (portiune consecutiva) si diferenta fata de subsir
  • Vectorul de sume partiale: construire O(n), interogare suma(l,r) in O(1) cu formula sp[r+1] - sp[l]
  • Tehnica generala pentru cea mai lunga secventa cu proprietate: O(n), O(1) memorie, o singura parcurgere
  • Algoritmul Kadane pentru secventa de suma maxima: O(n), initializare cu v[0], nu cu 0
  • Numararea subsecventelor cu suma data: O(n²) cu sume partiale

Urmatoarea lectie

Continua cu Lectia 4 pentru a invata despre matrici (tablouri bidimensionale) si parcurgerile lor.

Continua →