128. House Robber
Select houses to maximize the sum of their money values, with the restriction that no two selected houses are adjacent. Choosing no house is permitted.
You may skip any number of houses, and an unselected house can separate two selected ones. You are choosing a valid subset, not a contiguous range.
Example 1
Input
nums=[2,7,9,3,1]
Output
12
Explanation: Indices 0,2,4 give 2+9+1=12. The largest single house is not a complete optimum.
Example 2
Input
nums=[2,1,1,2]
Output
4
Explanation: Take both endpoints. Selecting the first locally large house and then the next available one need not be optimal.
Example 3
Input
nums=[1,2,3,1]
Output
4
Explanation: Take indices 0 and 2. The best prefix does not have to include its last house.
Example 4
Input
nums=[2147483647,0,2147483647]
Output
4294967294
Explanation: Nonadjacent endpoint values sum beyond int and require long arithmetic.
Constraints
0 <= nums.length <= 1050 <= nums[i] <= 231 - 1
Hints
Hint 1
Divide feasible subsets according to whether they contain the final house.
Hint 2
If you take index i, which prefix remains compatible? If you skip it, which prefix remains?
Hint 3
Compute max(previousOne, previousTwo+nums[i]) using the old registers, then shift.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Skip and take can win at different houses
[2,7,9,3,1]
12