题目内容

你是一名职业窃贼，计划对一条街道上的连续房屋实施盗窃。每间房屋中都放有一些现金。沿街每间房屋都安装了防盗系统，且相邻房屋的防盗系统相互联通。如果同一个夜晚相邻的两间房屋都被闯入，防盗系统就会自动报警。

给定一个非负整数数组 nums，其中 nums[i] 表示第 i 间房屋中存放的现金金额。请计算在不让防盗系统报警的情况下，一个夜晚能够获取的最大总金额。

约束条件：

• 数组 nums 的长度不小于 $1$，且不超过 $100$。
• 数组中每个元素 nums[i] 的取值范围为 $0$ 到 $400$。

输入描述

输入包含一个参数：一个非负整数数组 nums，表示沿街每间房屋中存放的现金金额。

输出描述

返回一个整数，表示在不触发相邻房屋防盗系统报警的情况下，一个夜晚能够偷取的最大总金额。

样例1

输入

0

输出

0

说明

只有一间房屋，金额为 0。 在不触发报警的情况下，最大总金额就是 0。

样例2

输入

4 5

输出

5

说明

两间房屋相邻，不能同时偷。 选择金额较高的第 2 间房屋，金额为 5，因此最大总金额为 5。

样例3

输入

2 1 1 2

输出

4

说明

可以选择第 1 间和第 4 间房屋，金额分别为 2 和 2。 这两间房屋不相邻，不会触发报警，总金额为 $2+2=4$。 因此最大总金额为 4。