House robber

Problem Given non-negative amounts in a row of houses, maximize the total robbed without taking two adjacent houses.

Input / Output

• Input: int array nums. Output: max sum.

Constraints

• n up to 100 classically; O(n) time, O(1) space expected.

Example

• [2,7,9,3,1] → 12 (2 + 9 + 1); [1,2,3,1] → 4.