你是一个经验丰富的小偷,准备偷沿湖的一排房间,每个房间都存有一定的现金,为了防止被发现,你不能偷相邻的两家,即,如果偷了第一家,就不能再偷第二家,如果偷了第二家,那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形,即第一个房间和最后一个房间视为相邻。 给定一个长度为n的整数数组nums,数组中的元素表示每个房间存有的现金数额,请你计算在不被发现的前提下最多的偷窃金额。 数据范围:数组长度满足 ,数组中每个值满足
输入描述:
第一行输入一个正整数 n ,表示数组的长度。第二行输入 n 个正整数,表示每个房间存有的现金。


输出描述:
输出最多的偷窃金额
示例1

输入

4
1 2 3 4

输出

6

说明

最优方案是偷第 2 4 个房间       
示例2

输入

3
1 3 6

输出

6

说明

由于 1 和 3 是相邻的,因此最优方案是偷第 3 个房间       
加载中...