Maksimum cəm oyunu#5865
sayda kart istifadəçiyə soldan sağa doğru sırayla düzülmüşdür. Hər bir kartda tam ədəd yazılmışdır. İki oyunçu növbə ilə bir kart götürür. Bu zaman yalnız ilk kartı və ya son kartı götürmək olar. Bütün kartlar götürüldükdən sonra oyun bitmiş sayılır (kartlar olduğu müddətdə oyunçu mütləq hər hansı mümkün gediş etməlidir). Oyunun məqsədi, götürülmüş kartlardakı ədədlərin cəmini maksimum etməkdir.
Birinci oyunçu hansı maksimal cəmi əldə edə biləcəyinə zəmanət verilir?
İlk sətirdə kartların sayı (1 \le N \le 2013) verilir. İkinci sətirdə boşluqla ayrılmış ədəd verilir (modulca 10^3-ü aşmayan) — kartlar üzərindəki ədədlər.
Birinci oyunçunun toplaya biləcəyi və buna zəmanət verilən yeganə tam ədədi — maksimal cəmi verin.
Nümunə 1
Əgər birinci gedişdə götürülərsə, onda rəqib cavab olaraq ya , ya da götürməlidir. Bu halların hər birində birinci oyunçu özünə götürə biləcək, beləliklə zəmanətli cəm 10-dur (bundan sonra ikinci oyunçu sonuncu kartı götürür və oyun bitir).
Əgər birinci oyunçu ilk gedişdə götürsəydi, ikinci oyunçu cavab olaraq götürə bilərdi və nəticədə birinci oyunçu yalnız 3 + 2 = \textbf{5} əldə etmiş olurdu. İkinci oyunçu sadəlövh bir gediş edərək "3" gedişinə "1" gedişi ilə cavab verə bilərdi. Bu zaman birinci oyunçu 3 + 9 = \textbf{12} cəmini əldə edə bilərdi. Lakin birinci oyunçu zəmanət verə bilməz ki, ikinci oyunçu bu qədər sadə bir gediş edər, ona görə də cavab deyil, -dur.