#1045. 巨石阵

巨石阵

题目描述

大嘴猴在森林里发现了一个神奇的排成一排的巨石阵。每晚在每块巨石上都会出现若干根好吃的香蕉,当太阳升起时,所有香蕉就会消失。大嘴猴发现一个规律,如果它拿走相邻两块巨石上的香蕉,那么巨石阵很久都不会出产香蕉。大嘴猴想知道,在每晚都能吃到香蕉的情况下,一晚能拿走的最多的香蕉数量。

输入格式

输入共两行 第一行1个正整数n,表示巨石的数量第二行n个非负整数,以空格分隔,表示每块巨石上的香蕉数量stone[i]

输出格式

输出共一行
第一行1个整数,表示大嘴猴一晚最多能拿走的香蕉数量

4
5 3 7 2
12
6
3 9 7 2 5 1
15

提示

数据范围与约定0 <n<= 100,0 <= stone[i] <= 400

样例1解释拿走1号巨石上的香蕉 (香蕉数量 = 5) ,然后拿走3号巨石上的香蕉 (香蕉数量 = 7)。一晚能拿走香蕉的最高数量 = 5 + 7 = 12 。

样例2解释拿走1号巨石上的香蕉(香蕉数量 = 3), 然后拿走3号巨石上的香蕉 (香蕉数量 = 7),然后拿走5号巨石上的香蕉 (香蕉数量 = 5)。一晚能拿走香蕉的最高数量 = 3 + 7 + 5 = 15 。