99. 選數字3

0 Judge

Code: 0


選數字3

有一個陣列$a[1]\cdots a[N]$。現在要選擇其中的一些數,相鄰的有選到的數會形成一組,例如選了$a[2],a[3],a[4],a[5],a[7],a[10],a[11]$,會形成三組。請問所有選法當中,「選到的數的總和」乘以「組數」的最大值是多少?

輸入

第一行有一個正整數$N$。($1\leq N \leq 2000$)

第二行有$N$個正整數$a[1]\cdots a[N]$。($1\leq a[i] \leq 1000$)

輸出

所有選法當中,「選到的數的總和」乘以「組數」的最大值。

子任務

子任務一(10%):$1\leq N \leq 3$

子任務二(30%):$1\leq N \leq 17$

子任務三(60%):無特別限制

範例輸入1

5
3 1 2 4 4

範例輸出1

27

範例輸入2

5
3 1 2 5 4

範例輸出2

28

範例輸入3

17
3 3 2 4 1 7 4 5 2 3 1 6 2 1 5 3 3

範例輸出3

328

提示

範例1:選擇$a[1],a[3],a[5]$,共形成三組,相乘為$9\times 3=27$。

範例2:選擇$a[1],a[3],a[4],a[5]$,共形成兩組,相乘為$14\times 2=28$。

範例3:唯一的最佳方案是選擇$a[1],a[2],a[4],a[6],a[8],a[10],a[12],a[13],a[15],a[17]$。


Judge Setting

run-time limit: 1000 ms
memory limit: 512000000 byte
測資數量: 31