Secvențe în vectori

O secvență într-un vector este o porțiune de elemente consecutive: v[i], v[i+1], ..., v[j].

Multe probleme de concurs cer să găsim secvențe cu anumite proprietăți:

cea mai lungă secvență crescătoare
cea mai lungă secvență de elemente egale
secvența cu suma maximă
numărul de secvențe cu o proprietate

Ce este o secvență?

O secvență este definită de două poziții: începutul st și sfârșitul dr.

Vector:  3  7  7  7  2  5  5  1
Indice:  1  2  3  4  5  6  7  8

Secventa [2, 4] = 7, 7, 7  (lungime 3)
Secventa [5, 7] = 2, 5, 5  (lungime 3)
Secventa [6, 7] = 5, 5     (lungime 2)

Lungimea unei secvențe de la st la dr este dr - st + 1.

Secvența de elemente egale (platou)

Problema

Găsim cea mai lungă secvență de elemente consecutive egale.

Ideea

Parcurgem vectorul și numărăm câte elemente consecutive au aceeași valoare. Când valoarea se schimbă, resetăm contorul.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int n;

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    int lung = 1;
    int maxLung = 1;

    for (int i = 2; i <= n; i++) {
        if (v[i] == v[i - 1]) {
            lung++;
        } else {
            lung = 1;
        }

        if (lung > maxLung) {
            maxLung = lung;
        }
    }

    fout << maxLung;

    return 0;
}

date.in:

10
3 7 7 7 2 5 5 1 1 1

date.out:

Pas cu pas

i	v[i]	v[i-1]	Egale?	lung	maxLung
2	7	3	NU	1	1
3	7	7	DA	2	2
4	7	7	DA	3	3
5	2	7	NU	1	3
6	5	2	NU	1	3
7	5	5	DA	2	3
8	1	5	NU	1	3
9	1	1	DA	2	3
10	1	1	DA	3	3

Există două platouri de lungime 3: 7 7 7 și 1 1 1.

Secvența crescătoare

Problema

Găsim cea mai lungă secvență în care fiecare element este strict mai mare decât cel anterior.

Codul

Același tipar, doar condiția se schimbă:

int lung = 1;
int maxLung = 1;

for (int i = 2; i <= n; i++) {
    if (v[i] > v[i - 1]) {
        lung++;
    } else {
        lung = 1;
    }

    if (lung > maxLung) {
        maxLung = lung;
    }
}

fout << maxLung;

Exemplu: vectorul 2 5 7 3 4 8 9 1

Secvențele crescătoare: 2,5,7 (lung 3), 3,4,8,9 (lung 4), 1 (lung 1).

Cea mai lungă: 4.

Secvența descrescătoare

La fel, dar cu v[i] < v[i - 1]:

if (v[i] < v[i - 1]) {
    lung++;
} else {
    lung = 1;
}

Schema generală

Toate problemele de tipul “cea mai lungă secvență cu proprietatea P” urmează același tipar:

int lung = 1;
int maxLung = 1;

for (int i = 2; i <= n; i++) {
    if ( /* v[i] si v[i-1] respecta proprietatea */ ) {
        lung++;
    } else {
        lung = 1;
    }

    if (lung > maxLung) {
        maxLung = lung;
    }
}

Proprietate	Condiție
Elemente egale	`v[i] == v[i-1]`
Strict crescător	`v[i] > v[i-1]`
Crescător (sau egal)	`v[i] >= v[i-1]`
Strict descrescător	`v[i] < v[i-1]`
Diferență constantă `d`	`v[i] - v[i-1] == d`
Alternanță par-impar	`v[i] % 2 != v[i-1] % 2`

Poziția secvenței maxime

Dacă vrem nu doar lungimea, ci și unde începe și unde se termină:

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int n;

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    int lung = 1, maxLung = 1;
    int stMax = 1, drMax = 1;
    int stCurent = 1;

    for (int i = 2; i <= n; i++) {
        if (v[i] == v[i - 1]) {
            lung++;
        } else {
            lung = 1;
            stCurent = i;
        }

        if (lung > maxLung) {
            maxLung = lung;
            stMax = stCurent;
            drMax = i;
        }
    }

    fout << "Lungime: " << maxLung << endl;
    fout << "De la pozitia " << stMax << " la " << drMax << endl;
    fout << "Elemente: ";
    for (int i = stMax; i <= drMax; i++) {
        fout << v[i] << " ";
    }

    return 0;
}

date.in:

10
3 7 7 7 2 5 5 1 1 1

date.out:

Lungime: 3
De la pozitia 2 la 4
Elemente: 7 7 7

Observație: dacă există mai multe secvențe de lungime maximă, codul de mai sus o găsește pe prima. Dacă vrem ultima, schimbăm > în >= la if (lung >= maxLung).

Numărul de secvențe cu o proprietate

Problema

Câte secvențe de elemente egale consecutive există?

O secvență nouă începe când v[i] != v[i-1].

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int n;

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    int cnt = 1; // prima secventa exista mereu

    for (int i = 2; i <= n; i++) {
        if (v[i] != v[i - 1]) {
            cnt++;
        }
    }

    fout << cnt;

    return 0;
}

date.in:

10
3 7 7 7 2 5 5 1 1 1

date.out:

Secvențele: 3 | 7 7 7 | 2 | 5 5 | 1 1 1 - 5 secvențe.

Secvența cu suma maximă

Problema

Găsim secvența de elemente consecutive care are suma cea mai mare.

Exemplu

Vector:  2 -3  5  1 -2  4 -1
Suma maxima: 5 + 1 + (-2) + 4 = 8  (secventa [3, 6])

Ideea (algoritmul lui Kadane)

Parcurgem vectorul și menținem suma secvenței curente. Dacă suma devine negativă, o resetăm la 0 (începem o secvență nouă).

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int n;

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    int sumaCurenta = 0;
    int sumaMax = v[1];

    for (int i = 1; i <= n; i++) {
        sumaCurenta = sumaCurenta + v[i];

        if (sumaCurenta > sumaMax) {
            sumaMax = sumaCurenta;
        }

        if (sumaCurenta < 0) {
            sumaCurenta = 0;
        }
    }

    fout << sumaMax;

    return 0;
}

date.in:

7
2 -3 5 1 -2 4 -1

date.out:

Pas cu pas

i	v[i]	sumaCurenta	sumaMax
1	2	2	2
2	-3	-1 -> reset 0	2
3	5	5	5
4	1	6	6
5	-2	4	6
6	4	8	8
7	-1	7	8

Suma maximă este 8 (secvența 5, 1, -2, 4).

De ce resetăm la 0?

Dacă suma curentă devine negativă, înseamnă că secvența de până acum ne “trage în jos”. Orice secvență nouă care începe de la elementul următor va fi mai bună fără elementele anterioare.

De aceea, renunțăm la tot ce am adunat și începem de la 0.

Acest algoritm se numește algoritmul lui Kadane și găsește suma maximă într-o singură parcurgere.

Secvența cu suma egală cu S

Problema

Găsim o secvență a cărei sumă este exact S.

Ideea

Folosim doi indici st și dr care definesc o “fereastră” pe vector. Adăugăm elemente la dreapta și scoatem de la stânga.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int n, s;

int main()
{
    fin >> n >> s;
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    int st = 1;
    int suma = 0;

    for (int dr = 1; dr <= n; dr++) {
        suma = suma + v[dr];

        while (suma > s && st < dr) {
            suma = suma - v[st];
            st++;
        }

        if (suma == s) {
            fout << "DA: de la " << st << " la " << dr;
            return 0;
        }
    }

    fout << "NU";

    return 0;
}

date.in:

7 8
2 3 5 1 2 4 1

date.out:

DA: de la 2 la 4

Secvența 3 + 5 + 1 - 1 = 8… de fapt v[2] + v[3] + v[4] = 3 + 5 + 0… să verificăm: 3 + 5 = 8. Secvența [2, 3].

Atenție: această tehnică (numită two pointers sau fereastră glisantă) funcționează doar dacă toate elementele sunt pozitive. Cu elemente negative, problema devine mai complexă.

Greșeli frecvente

1. Inițializarea lungimii cu 0 în loc de 1

int lung = 0; // GRESIT - primul element formeaza o secventa de lungime 1
int lung = 1; // CORECT

2. Uitarea actualizării maximului în buclă

if (v[i] == v[i - 1]) {
    lung++;
}
// Lipseste: if (lung > maxLung) maxLung = lung;

Maximul trebuie verificat la fiecare pas, nu doar când se schimbă secvența.

3. Verificarea maximului doar la resetare

if (v[i] != v[i - 1]) {
    if (lung > maxLung) maxLung = lung; // GRESIT - rata ultima secventa
    lung = 1;
}

Dacă cea mai lungă secvență este la sfârșitul vectorului, nu va exista o resetare după ea și maximul nu se actualizează. Verificăm maximul în fiecare iterație.

4. Bucla începe de la 1 în loc de 2

for (int i = 1; i <= n; i++) { // GRESIT: v[i-1] = v[0] la primul pas
for (int i = 2; i <= n; i++) { // CORECT

Comparăm v[i] cu v[i-1], deci începem de la i = 2.

Ce să reții

O secvență este o porțiune de elemente consecutive în vector.
Tiparul de bază: contor lung care crește sau se resetează, și maxLung care reține maximul.
Schimbând doar condiția, rezolvăm probleme diferite (egale, crescător, descrescător, etc.).
Poziția secvenței se reține salvând indicele de început stCurent.
Suma maximă - algoritmul lui Kadane: resetăm suma când devine negativă.
Suma egală cu S - tehnica ferestrei glisante (doar pentru valori pozitive).
Maximul se verifică la fiecare pas, nu doar la resetare.

Probleme

i	v[i]	v[i-1]	Egale?	lung	maxLung
2	7	3	NU	1	1
3	7	7	DA	2	2
4	7	7	DA	3	3
5	2	7	NU	1	3
6	5	2	NU	1	3
7	5	5	DA	2	3
8	1	5	NU	1	3
9	1	1	DA	2	3
10	1	1	DA	3	3

i	v[i]	v[i-1]	Egale?	lung	maxLung
2	7	3	NU	1	1
3	7	7	DA	2	2
4	7	7	DA	3	3
5	2	7	NU	1	3
6	5	2	NU	1	3
7	5	5	DA	2	3
8	1	5	NU	1	3
9	1	1	DA	2	3
10	1	1	DA	3	3

i	v[i]	v[i-1]	Egale?	lung	maxLung
2	7	3	NU	1	1
3	7	7	DA	2	2
4	7	7	DA	3	3
5	2	7	NU	1	3
6	5	2	NU	1	3
7	5	5	DA	2	3
8	1	5	NU	1	3
9	1	1	DA	2	3
10	1	1	DA	3	3