Description
Maximize stolen value from nonadjacent houses on a circle. The first and last houses are adjacent.
Solution
def rob(nums):
if len(nums) == 1:
return nums[0]
def line(start, end):
previous = current = 0
for i in range(start,end):
previous, current = current, max(current,previous+nums[i])
return current
return max(line(0,len(nums)-1), line(1,len(nums)))Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[2,3,2]]- Output
3
The two houses valued 2 are adjacent around the circle.
Example 2
- Input
[[1]]- Output
1
The sole house is a special case.
Example 3
- Input
[[2,1,1,2]]- Output
3
The two end houses cannot both be taken.
Approach
Solve two linear ranges: omit the first house or omit the last, and take the larger result.
Time & space
O(n) time; O(1) space. Here n is the input length.