今天,臺大程式解題社的其中 $N$ 位選手面向你站成了一個橫排,由左至右的編號為 $1\sim N$,身為這次活動負責人的你,被社長指派必須挑出一些人站出來進行機智問答,這些站出來的人只會往你的方向前進一步,並不會左右移動。不過,邪惡的社長為了增添你的麻煩,特別告訴你說你選出來參加問答的人選必須要滿足以下條件:
你已經知道有幾種挑人的方法,因此調查了一遍每個人的問答能力值,分別為 $a_1, a_2, \ldots, a_N$,代表若第 $i$ 個人被挑選出來參加機智問答,他可以讓總能力值增加 $a_i$,注意到有些人的能力值是負的,代表你挑選他出來參加機智問答反而會讓總能力值變小(可能是因為他身體不舒服吧!)。
現在你的目標是要最大化挑選出來的人的總能力值,請問這個最大值會是多少呢?
輸入首行有一個正整數 $N$,代表站在你面前的選手數。
次行 $N$ 個整數 $a_1, a_2, \ldots, a_N$,代表第 $i$ 個人的能力值為 $a_i$
輸出挑選出來的人的總能力值最大會是多少。
程式解題社教學題。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資。 | 0 |
2 | 0~8 | 無特別限制。 | 100 |