1189 - 打家劫舍

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

给定一个代表每个房屋存放金额的非负整数数组nums,计算你不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

输入

第一行输入整数n,表示有n个房间

以下n行表示每个房间存放的金额

输出

一个整数,表示偷窃到的最高金额

样例

输入

4
1 2 3 1

输出

4

提示

1 \leq n \leq 100

0 \leq nums[i] \leq 400

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题