主唱太拼命了
今天,臺大程式解題社的其中 N 位選手面向你站成了一個橫排,由左至右的編號為 1∼N,身為這次活動負責人的你,被社長指派必須挑出一些人站出來進行機智問答,這些站出來的人只會往你的方向前進一步,並不會左右移動。不過,邪惡的社長為了增添你的麻煩,特別告訴你說你選出來參加問答的人選必須要滿足以下條件:
你已經知道有幾種挑人的方法,因此調查了一遍每個人的問答能力值,分別為 a1,a2,…,aN,代表若第 i 個人被挑選出來參加機智問答,他可以讓總能力值增加 ai,注意到有些人的能力值是負的,代表你挑選他出來參加機智問答反而會讓總能力值變小(可能是因為他身體不舒服吧!)。
現在你的目標是要最大化挑選出來的人的總能力值,請問這個最大值會是多少呢?
輸入首行有一個正整數 N,代表站在你面前的選手數。
次行 N 個整數 a1,a2,…,aN,代表第 i 個人的能力值為 ai
輸出挑選出來的人的總能力值最大會是多少。
程式解題社教學題。