Se citesc n numere naturale asezate in CERC (primul si ultimul element sunt considerate vecine). Determinati, folosind Programarea Dinamica, suma maxima ce se poate obtine alegand o submultime de elemente astfel incat niciodata doua elemente vecine (in sensul circular) sa nu fie alese simultan.
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citesc cele n numere.
- Date de iesire
- Se afiseaza un singur numar: suma maxima obtinuta.
- Restrictii
- 1 <= n <= 100000, 0 <= element <= 10^4
Exemple
Exemplul 1
Intrare
4 1 2 3 1
Iesire
4
Exemplul 2
Intrare
1 5
Iesire
5