Soluție: faliment

Dacă scădem pasivele din active pentru fiecare client, obținem un șir de numere care reprezintă valoarea clienților. Problema se reduce la a determina o secvență din șir (elemente aflate pe poziții consecutive) care să aibă suma maximă.

Există o soluție simplă: încercăm toate variantele și o alegem pe cea cu suma cea mai mare. Ordinul de complexitate este însă O(n3).

Am putea reduce destul de simplu complexitatea la O(n2) dacă am calcula șirul S al sumelor primelor i elemente din șir, operațile care poate fi efectată în timp liniar. Valoarea totală a clienților cuprinși între două poziții P și Q va fi dată de diferența SQ - SP-1; vom considera S0 = 0.

Dar, putem ajunge și la o soluție liniară. Se observă destul de ușor că valoarea totală a celei mai bune secvențe care se termină la poziția i este dată fie de valoarea elementului respectiv, fie de valoarea totală a celei mai bune secvențe care se termină la poziția i - 1 la care se adaugă valoarea elementului respectiv. Practic, adunăm secvența anterioară doar dacă valoarea sa totală este pozitivă. Așadar, dacă notăm cu C șirul valorilor clienților, calculăm un șir V în care avem Vi = max(Vi-1, 0) + Ci. Rezultatul problemei va fi dat de valoarea maximă a elementelor din V; vom considera V0 = 0.

Ar mai putea fi menționat faptul că șirul V nu trebuie neapărat păstrat; pentru a calcula valoarea unui element avem nevoie doar de valoarea elementului anterior, iar maximul poate fi determinat pe parcurs.

Te-ar putea interesa și: