题目描述

假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且当相邻的两个房子同一天被打劫时，该系统会自动报警。

给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，在不触动报警装置的情况下, 你最多可以得到多少钱 。

输入格式

第一行1个整数$n$,表示房屋数量

第二行，$n$个非负整数，表示房屋里的钱

输出格式

1个整数，表示最多可以得到的钱

3
3 8 4

8

解释：仅仅打劫第二个房子

4
5 2 1 3

8

解释：抢第一个和最后一个房子

挑战

$O(n)$ 时间复杂度 且 $O(1)$ 存储

数据范围

$n\leqslant200$

来源

lintcode 392