A street has a row of houses, and nums[i] is the cash in house i. You may take the cash from any set of houses as long as no two chosen houses are next to each other. Return the largest total you can collect.
Implement rob(nums: list[int]) -> int.
rob([2, 7, 9, 3, 1]) # 12 (2 + 9 + 1)
rob([6, 1, 1, 6]) # 12 (6 + 6: skipping two in a row is allowed)
rob([]) # 0
Constraints: 0 <= len(nums) <= 10^5, 0 <= nums[i] <= 10^4.
Trying every subset is exponential; aim for O(n) time and O(1) extra space.
Show hint
For the best total over the first i houses, house i is either taken or skipped, and each choice leaves a smaller version of the same question.