Problem
You are a robber on a street. Adjacent houses have alarms — you can’t rob two adjacent. Maximize loot.
Example
Input: [2,7,9,3,1]
Output: 12
Rob houses 0, 2, 4: 2+9+1.Solution
DP: rob[i] = max(rob[i-1], rob[i-2] + nums[i]). Compress to two variables for O(1) space.
def rob(nums):
prev, curr = 0, 0
for n in nums:
prev, curr = curr, max(curr, prev + n)
return currfunction rob(nums) {
let prev = 0, curr = 0;
for (const n of nums) {
[prev, curr] = [curr, Math.max(curr, prev + n)];
}
return curr;
}int rob(vector<int>& nums) {
int prev = 0, curr = 0;
for (int n : nums) {
int next = max(curr, prev + n);
prev = curr;
curr = next;
}
return curr;
}public int rob(int[] nums) {
int prev = 0, curr = 0;
for (int n : nums) {
int next = Math.max(curr, prev + n);
prev = curr;
curr = next;
}
return curr;
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
At each house, decide: skip and keep previous max, OR rob this house plus max from two houses ago. Track only the last two values.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?