Problem Statement
You are a robber planning to rob houses along a street. Each house has money stashed. Adjacent houses have security systems connected - if two adjacent houses are broken into, the police will be alerted.
Given an integer array nums representing money in each house, return the maximum amount you can rob tonight without alerting police.
Approach
Dynamic programming: at each house, choose to rob it (plus max from houses before previous) or skip it (max from previous house).
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
Examples
Example 1
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 and 3: 1 + 3 = 4
Example 2
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1, 3, and 5: 2 + 9 + 1 = 12
Constraints
- ▸
1 <= nums.length <= 100 - ▸
0 <= nums[i] <= 400
Loading...
Sign in to run your code...
Asked by companies:
AmazonGoogleMicrosoftCisco