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.

Expected approach

• DP with two rolling values: best including the previous house vs excluding it — take = skip + nums[i]; skip = max(take_prev, skip_prev). O(n)/O(1). Escalations to expect: House Robber II (circular street — run twice excluding first/last), III (houses on a tree — post-order DP returning rob/skip pair). Recognize each is the same include/exclude recurrence on a different topology.