取数

时间限制:1s 内存限制:64MB

问题描述

有n个数(2≤n≤100)排成一排,从n个数中任取若干个数,取数规则为每次取相邻的2个数,不能取1个,也不能取多于2个连续的数,找一种取法,使取到数的和为最大。

例如:n=6,6个数

13  2  17  14  8  16

取数方法有

13  2   14  8   和为 37

13  2   8   16  和为 39

2   17  8   16  和为 43

17  14          和为 31

其中和最大的为43

输入描述

输入文件名为:data.in

输入文件格式:第1行一个整数n,第2行n个整数(1≤i≤100)

n       
x1  x2…….xn           

输出描述

包含一个整数,即合理取法中最大的和。

样例输入

6
13 2 17 14 8 16

样例输出

43

题目来源

2014年江苏省小学生夏令营