Course launching October 2020
Follow me on YouTube for free coding interview videos.
Users who sign up for the email list will receive an exclusive 75% discount at launch.
THIS NEEDS AN UPDATE. DESCRIBE THE DYNAMIC PROGRAMMING EVEN MORE. Check NOTES.md
In an alternate reality, you decided to use your powers for evil instead of good and started stealing packages. You know exactly how much each package is valued at, so you can walk down the street and pick up the best ones. The only issue is that with all the connected smart homes, if you rob two houses in a row, it will automatically call the police.
Write a function
stealPackages that returns maximum amount you can earn without having the police called.
The houses are represented as an array where the items the value of a package at their house. You can't rob any two houses that are next to each other in the array because it will call the police.
const packageValues = [2, 3, 5, 1]; stealPackages(packageValues); // 7 // You would steal packages at index 0 and 2 const packageValues = [1, 10, 3, 2, 5]; stealPackages(packageValues); // 15 // You would steal packages at index 1 and 4
Validate My Answer
You can reasonably assume a package values is
> 0. It would never be negative because you wouldn't leave money, and zero is just a no-op.
This may seem intimidating at first, but we can simplify it to subproblems. At any point, we only care about adjacent houses. We just need to know if there is a larger max profit by stealing the current house's packages or its adjacent packages.
By using bottom-up dynamic programming, you can solve this in O(n) time and O(1) space.
Make sure your solution handles an array with zero or one item.