← 返回 amazon 的题目列表House Robber II
类型：online_judge
House Robber II
You are a robber planning to rob houses along a street. Each house contains some money. Adjacent houses are connected, and the first and last houses are also adjacent, forming a circle.
If two adjacent houses are robbed on the same night, the alarm is triggered. Given an integer array nums, where nums[i] is the amount of money in the i-th house, return the maximum amount that can be robbed without triggering the alarm.
Input Format
First line: an integer n, the number of houses.
Second line: n non-negative integers nums[0..n-1].
Output Format
Print one integer: the maximum amount that can be robbed.
Constraints
1 <= n <= 10^5
0 <= nums[i] <= 10^4
Example
Input:
3
2 3 2
Output:
3
Explanation: The first and last houses are adjacent, so they cannot both be robbed. The optimal choice is to rob only the second house.
Example
Input
3
2 3 2
Output
3