Asked at

House Robber

Medium
VerifiedArrayDynamic Programming~20 min

Houses sit in a row, each holding nums[i] money. You cannot rob two adjacent houses. Return the maximum you can take.

The input arrives as a single array nums. Return the max sum.

Examples

in[1, 2, 3, 1]
out4

Rob houses 0 and 2: 1 + 3 = 4.

in[2, 7, 9, 3, 1]
out12

Rob houses 0, 2, and 4: 2 + 9 + 1 = 12.

Constraints

  • 1 ≤ nums.length ≤ 100
  • 0 ≤ nums[i] ≤ 400
  • Target: O(n) time, O(1) space

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.