Zero To DSAZero To DSA
Privacy Policy
Climbing StairsCoin Change

House Robber

medium
Time: O(n)
Space: O(1)

You are a robber planning to rob houses along a street. Each house has a certain amount of money. Adjacent houses have security systems that will alert police if two adjacent houses are robbed. Return the maximum amount you can rob without alerting police.

Constraints

  • 1 <= nums.length <= 100

Examples

Input: nums = [1,2,3,1]
Output: 4
Rob house 1 (1) and house 3 (3). Total = 4.
Input: nums = [2,7,9,3,1]
Output: 12
Rob house 1 (2), house 3 (9), house 5 (1). Total = 12.