infoarena

Salut. Cum as putea sa rezolv urmatoare problema : Se dau n numere asezate sub forma de cerc. Sa se determine un subsir de suma maxima stiind ca nu se pot alege 2 numere consecutive (primul si ultimul se considera consecutive).

Eu am incercat urmatoarea dinamica dp[ i ]=suma maxima care se obtine pana la elementul i. Recurenta este
Si raspunsul era in dp[1]. Si nu e bine pentru ca nu tine cont ca n-am voie sa iau si primul si ultimul element. Cum as putea sa adaptez si pentru cazul asta ? Sau daca nu se poate cum s-ar rezolva altfel ?

Daca ai a[1..n] poti incerca sa faci dinamica pentru a[1..n-1] si apoi pentru a[2..n] si iei maximul. Si in relatia de recurenta cred ca trebuie sa fie
pentru ca s-ar putea sa ajungi la o suma negativa si atunci nu vrei sa selectezi acele elemente (ca si la subsecventa de suma maxima).

Pot fi și numere negative, nu?

Multumesc George a mers asa. \:D/ Nu, in problema mea nu apareau si numere negative, de aceea nu luam in calcul cazul in care ajung la suma negativa.