House Robber II

Problem Statement

You are a professional thief planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at each location have the same amount of money stashed. The only constraint stopping you from robbing houses on the same street is that you can't rob two consecutive houses.

Given a list of non-negative integers, representing the amount of money in each house, determine the maximum amount of money you can rob tonight.

Rules and Constraints

• The list of integers only represents the number of houses, and each house corresponds to a certain amount of money.
• The list is 1-indexed, but it can be 0-indexed without losing generality.
• There are at least two houses.
• Each house can either be robbed or skipped.
• You cannot rob two consecutive houses.

Input

A list of non-negative integers representing the amount of money in each house.

Output

The maximum amount of money that can be robbed.

Time Complexity

The solution should have a time complexity that scales linearly with the number of houses.

Space Complexity

The solution should have a space complexity that is optimal and does not use more space than necessary.

Example

Input: {"input_data":[1,2,3]} Output: [1,2,3]