Subsecvența cu suma maximă (Kadane 1D)

Algoritmul lui Kadane rezolvă una dintre cele mai clasice probleme pe vectori:

dintre toate secvențele de elemente consecutive, care are suma maximă?

Această problemă apare foarte des în concursuri și este importantă și pentru lecția despre Kadane 2D, unde ideea se extinde la matrici.

Problema

Avem un vector v[1..n] cu numere pozitive și negative. Vrem să găsim:

• suma maximă a unei subsecvențe consecutive

O subsecvență consecutivă înseamnă un interval de forma:

v[st], v[st + 1], ..., v[dr]

unde 1 <= st <= dr <= n.

Exemplu

Vector: 2 -3 5 1 -2 4 -1

Subsecvența optimă este:

5 1 -2 4

Suma ei este:

5 + 1 + (-2) + 4 = 8

Deci răspunsul este 8.

Forța brută

Am putea încerca toate intervalele [st, dr]:

• alegem st
• alegem dr
• calculăm suma pe interval

int maxim = v[1];

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

Complexitate: O(n²).

Pentru n mare, este prea lent.

Ideea lui Kadane

Parcurgem vectorul de la stânga la dreapta și menținem:

• sumaCurenta = suma celei mai bune secvențe care se termină în poziția curentă
• sumaMax = cea mai bună sumă găsită până acum

La fiecare element v[i], avem două opțiuni:

1. continuăm secvența anterioară
2. începem o secvență nouă din v[i]

Dacă suma acumulată până acum este negativă, ea nu ne ajută. Mai bine o abandonăm și pornim din nou.

Varianta clasică

#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:

8

Pas cu pas

Pentru vectorul:

2 -3 5 1 -2 4 -1

Răspuns final: 8.

De ce resetăm suma la 0?

Dacă sumaCurenta < 0, atunci orice secvență viitoare care ar continua de aici ar fi mai slabă decât una care începe direct de la următorul element.

Exemplu:

sumaCurenta = -5
următorul element = 7

Dacă continuăm, obținem:

-5 + 7 = 2

Dar dacă începem direct cu 7, obținem:

7

Clar este mai bine să aruncăm suma negativă.

Cazul cu toate elementele negative

Acesta este cazul unde mulți greșesc.

Exemplu:

-8 -3 -5 -10

Răspunsul corect nu este 0, ci -3, pentru că subsecvența trebuie să fie nevidă.

De aceea inițializăm:

int sumaMax = v[1];

nu:

int sumaMax = 0; // GREȘIT

Varianta robustă

O variantă foarte clară și sigură este:

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

for (int i = 2; i <= n; i++) {
    if (sumaCurenta + v[i] > v[i])
        sumaCurenta = sumaCurenta + v[i];
    else
        sumaCurenta = v[i];

    if (sumaCurenta > sumaMax)
        sumaMax = sumaCurenta;
}

Aceasta spune explicit:

• ori continui secvența anterioară
• ori pornesc una nouă din v[i]

Este echivalentă cu varianta clasică.

Aflarea pozițiilor intervalului optim

Uneori nu ni se cere doar suma maximă, ci și intervalul [st, dr].

#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 = v[1];
    int sumaMax = v[1];

    int stCurent = 1;
    int stBest = 1, drBest = 1;

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

        if (sumaCurenta > sumaMax) {
            sumaMax = sumaCurenta;
            stBest = stCurent;
            drBest = i;
        }
    }

    fout << "Suma maxima: " << sumaMax << "\n";
    fout << "Interval: [" << stBest << ", " << drBest << "]";

    return 0;
}

Pentru:

2 -3 5 1 -2 4 -1

obținem:

Suma maxima: 8
Interval: [3, 6]

Exemplu complet

#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 << "\n";

    return 0;
}

date.in:

8
-2 1 -3 4 -1 2 1 -5

date.out:

6

Subsecvența optimă este:

4 -1 2 1

cu suma 6.

Complexitate

• Timp: O(n)
• Memorie suplimentară: O(1)

Parcurgem vectorul o singură dată.

Comparație

Kadane este optim pentru această problemă.

Legătura cu Kadane 2D

În varianta pe matrici, alegem două linii și comprimăm coloanele într-un vector. Apoi aplicăm exact acest algoritm pe acel vector.

De aceea, Kadane 1D este baza pentru Kadane 2D.

Greșeli frecvente

1. Inițializarea cu 0

int sumaMax = 0; // GREȘIT

Dacă toate valorile sunt negative, răspunsul devine greșit.

Corect:

int sumaMax = v[1];

2. Considerarea subsecvenței vide

În problema clasică, subsecvența trebuie să fie nevidă. Nu avem voie să alegem „nimic” doar ca să obținem suma 0.

3. Confuzia dintre „subsecvență” și „subșir”

La Kadane, elementele trebuie să fie consecutive.

Exemplu:

1 -100 2 3

Nu avem voie să alegem 1 2 3, pentru că nu sunt consecutive.

Subsecvențe valide:

• 1
• -100
• 2 3
• 1 -100 2

4. Uitarea pozițiilor

Dacă problema cere și intervalul optim, nu este suficient să calculăm doar suma. Trebuie să memorăm și:

• unde începe secvența curentă
• unde începe și se termină secvența optimă

Ce să reții

• Kadane găsește subsecvența consecutivă cu suma maximă.
• Ideea: dacă suma curentă devine negativă, o abandonăm.
• Complexitate: O(n).
• Inițializarea trebuie făcută cu v[1], nu cu 0.
• Algoritmul funcționează și când toate valorile sunt negative.
• Poate fi extins pentru a afla și intervalul [st, dr].
• Este baza pentru Kadane 2D.

Probleme

pbinfoSecvsummax→