Steal Packages

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.

Breakdown

Approach and test strategy

Choose or skip each package value without taking adjacent locations

Read the approach, boundary cases, and complexity

At each location, compare skipping it with taking its value plus the best result before the adjacent predecessor. Retain the best result for earlier prefixes rather than greedily choosing a locally largest value. A large middle value can change which neighboring choices remain possible. The empty prefix contributes zero, matching the no-package result.

Cases to check

Test no locations and one location.
For [2, 3, 5, 1], the best total is seven.
Include repeated values and an input where the best choice skips more than one location between selected values.

Cost model

A rolling-prefix DP uses O(n) time and O(1) auxiliary state when only the maximum total is required. Reconstructing selected locations requires additional retained decisions or another reconstruction strategy.

Programming languages for this lesson

Starter code and reference implementations are available in:

The editor shows which of these languages can run on this deployment.

Follow teacher

Table of Contents

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.

Follow teacher

Table of Contents

Test Results

Run your code and see results here...

/**
 * @param {List[int]} packageValues
 * @return {int}
 */
const stealPackages = (packageValues) => {
  // Your solution here
};

Steal Packages

Write a function stealPackages that returns the maximum amount you can earn without having the police called.

/**
 * @param {List[int]} packageValues
 * @return {int}
 */
const stealPackages = (packageValues) => {
  // Your solution here
};