Euro2
Povestea din enunt "ascunde" urmatoarea problema: sa se determine cel mai lung subsir care este crescator pana la o anumita pozitie, apoi este descrescator.
Problema se poate rezolva corect utilizand in mai multe feluri metoda programarii dinamice, dar rezolvarile vor avea performante diferite.
1. Cel mai simplu algoritm de tip brute force genereaza toate cele 2N submultimi ale multimii numerelor date, si le verifica pentru a decide daca au proprietatea ceruta. Aceasta solutie are o complexitate O(N * 2N).
2. Solutii mai performante obtinem utilizand algoritmi de determinare a celui mai lung subsir crescator (descrescator), apeland la metoda programarii dinamice. Rezolvarea corecta consta in determinarea lungimii celui mai lung subsir crescator considerand ca si capat al acestuia pe rand, fiecare element al sirului dat, si lungimea celui mai lung subsir descrescator considerand ca prim element al acestuia, pe rand, fiecare element al sirului dat. Avand aceste lungimi, prin combinarea lor si determinarea maximului sumelor perechilor de lungimi corespunzatoare, obtinem rezultatul in complexitate O(N). Lungimile mentionate se pot calcula cu unul din algoritmii cunoscuti avand complexitatile O(N2) sau, optim, O(Nlog2N).
