Log in to continue or upgrade to the full course
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 the maximum amount you can earn without having the police called.
The houses are represented as an array where each item in the array is an integer for the value of the package at that 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 value is
> 0. It would never be negative because you wouldn't leave money, and zero just wouldn't exist.
This may seem intimidating at first, but we can simplify it to subproblems. We can solve for the max profit at each house as we walk through the input. We have a decision to calculate the max profit for the current house where the choices are to either steal the current package and add it to the max profit from two houses back or keep the max profit from one house back.
By using bottom-up dynamic programming, you can solve this in O(n) time.
This is actually a special case where you don't need a dynamic programming data structure and can just use variables for the memoization in a bottom-up approach for O(1) space.
Make sure your solution handles an array with zero or one item.