You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint is that adjacent houses have security systems connected — you cannot rob two adjacent houses.
Given an integer array nums, return the maximum amount of money you can rob tonight.
Example 1
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (1) and house 3 (3).
Example 2
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1, 3, 5: 2+9+1=12.
1 <= nums.length <= 1000 <= nums[i] <= 400dp[i] = max(dp[i-1], dp[i-2] + nums[i])
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
int prev2 = nums[0];
int prev1 = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
int curr = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}Time: O(n) · Space: O(1)