59. House Robber

Medium · Dynamic Programming

You are a robber planning to rob houses along a street. Each house has a certain amount of money stashed. You cannot rob two adjacent houses (the security system will trigger an alarm). Given an array of non-negative integers representing the amount of money in each house, determine the maximum amount of money you can rob without alerting the police.

You must choose a subset of non-adjacent houses to maximize the total money stolen.

Examples

Example 1
Input: [1, 3, 1, 3, 100]
Output: 103
Explanation: Rob house at index 0 (money = 1), skip house at index 1, rob house at index 2 (money = 1), skip house at index 3, and rob house at index 4 (money = 100). Total = 1 + 1 + 100 = 102. Wait, actually rob house at index 1 (money = 3) and house at index 4 (money = 100) for total = 103.
Example 2
Input: [2, 7, 9, 3, 1]
Output: 12
Explanation: Rob house at index 0 (money = 2), skip house at index 1, rob house at index 2 (money = 9), and skip houses at indices 3 and 4. Total = 2 + 9 = 11. Actually, rob house at index 1 (money = 7) and house at index 3 (money = 3) for total = 10. Or rob house at index 2 (money = 9) and house at index 4 (money = 1) for total = 10. Best is to rob houses at indices 1 and 2: 7 + 9 = 16. Wait, we can't rob adjacent houses. So rob index 0 (2) and index 2 (9) = 11, or rob index 1 (7) and index 3 (3) = 10, or rob index 1 (7) and index 4 (1) = 8, or rob index 2 (9) and index 4 (1) = 10. Actually the best is index 0 (2), index 2 (9), index 4 (1) = 12.

Constraints