forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhouse_robber.py
More file actions
33 lines (24 loc) · 740 Bytes
/
house_robber.py
File metadata and controls
33 lines (24 loc) · 740 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
"""
House Robber
Determine the maximum amount of money that can be robbed from a row of
houses without robbing two adjacent houses.
Reference: https://leetcode.com/problems/house-robber/
Complexity:
Time: O(n)
Space: O(1)
"""
from __future__ import annotations
def house_robber(houses: list[int]) -> int:
"""Compute the maximum robbery amount without hitting adjacent houses.
Args:
houses: List of non-negative integers representing money in each house.
Returns:
Maximum amount that can be robbed.
Examples:
>>> house_robber([1, 2, 16, 3, 15, 3, 12, 1])
44
"""
last, now = 0, 0
for house in houses:
last, now = now, max(last + house, now)
return now