h307. 不相邻展品最大价值

题目描述

一排有 $n$ 件展品，第 $i$ 件价值为 $v_i$。可以选择任意多件展品，但不能同时选择位置相邻的两件。

求所选展品的最大总价值。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个非负整数 $v_1,v_2,\ldots,v_n$。

输出格式

输出一个整数，表示最大总价值。

数据范围

• $1\le n\le 100000$
• $0\le v_i\le 10000$

样例

6
5 1 2 10 6 2

17

标签：动态规划、线性动态规划