suma maxima

[•soriyn]

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

Cod:

daca i==n dp[i]=a[n];
altfel dp[i]=max(dp[i+1],a[i]+dp[i+2]);

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 ?

[•PlayLikeNeverB4]

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

Cod:

dp[i]=max(dp[i+1], a[i]+dp[i+2], a[i])

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).

[•psycho21r]

Pot fi și numere negative, nu?

[•soriyn]

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