Description
Choose nonadjacent houses on a line to maximize the sum of their nonnegative values.
Solution
def rob(nums):
previous = current = 0
for value in nums:
previous, current = current, max(current, previous+value)
return currentExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[3,2,5,1]]- Output
8
Taking 3 and 5 earns eight.
Example 2
- Input
[[8]]- Output
8
Take the sole house.
Example 3
- Input
[[0,0]]- Output
0
All available values are zero.
Approach
At each house choose between skipping it and taking it plus the best value two houses back.
Time & space
O(n) time; O(1) space. Here n is the input length.