题目描述

有一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，​如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警​。计算小偷在不触动警报装置的情况下​，一夜之内能够偷窃到的最高金额。

输入格式

第一行1个整数n，表示房屋的数量 接下来n个整数，表示每个房屋存放的金额(不超过400)

输出格式

输出一个整数，表示小偷能够偷窃到的最高金额

4
1 2 3 1

4

示例 1：

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

5
2 7 9 3 1

12

示例 2：

解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

• 1 <= n <= 100