46. 選數字2

0 Judge

Code: 0


選數字2

有一個陣列$a[1]\cdots a[N]$。現在可以從中選擇一些數,但是任兩個有選的數之間至少要隔著個沒選的數。請問所有選法裡面,所選的數的總和最大可以是多少?

輸入

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

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

輸出

所有選法裡面所選的數的最大總和。

子任務

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

子任務二(50%):無特別限制

範例輸入1

7
3 5 3 1 2 5 1

範例輸出1

10

提示

選擇$a[2]$和$a[6]$,有最大總和$10$。


Judge Setting

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