打家劫舍

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，但相邻的房屋装有相互连通的防盗系统——如果两间相邻的房屋在同一晚上被闯入，系统会自动报警。

给定一个非负整数数组，表示每个房屋存放的金额，请计算在不触动警报装置的前提下，一夜之内能够偷窃到的最高金额。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 100$），表示房屋数量。
第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq 400$），表示每间房屋内的现金金额。

输出格式

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

示例

示例 1

输入：

4
1 2 3 1

输出：

4

解释：
偷窃第 1 号房屋（金额 = 1），然后偷窃第 3 号房屋（金额 = 3），总金额 = 1 + 3 = 4。

示例 2

输入：

5
2 7 9 3 1

输出：

12

解释：
偷窃第 1 号（2）、第 3 号（9）和第 5 号房屋（1），总金额 = 2 + 9 + 1 = 12。

数据范围

• $1 \leq n \leq 100$
• $0 \leq a_i \leq 400$