Reducing a new problem to a solved one

When a constraint wraps around, split into cases where it does not, and reuse what you have.

Why it works

Split on the awkward element

Either the first element is taken or it is not. Those two cases are exhaustive, and in each one the circular constraint disappears.

If the first is taken, the last cannot be, so the problem is the linear one over everything except the last. If the first is not taken, the problem is the linear one over everything except the first.

Run the solved linear version twice and take the better answer. No new recurrence, no new state.

The linear version is the one you just wrote, in its rolling two-variable form. The only new work is deciding what to hand it.

1def linear_best(values):2    take, skip = 0, 03    for value in values:4        take, skip = skip + value, max(take, skip)5    return max(take, skip)6 7values = [1, 2, 3, 1]8print("everything:      ", values, "->", linear_best(values))9print("without the first:", values[1:], "->", linear_best(values[1:]))10print("without the last: ", values[:-1], "->", linear_best(values[:-1]))

Each slice removes one end, so neither run can ever take both ends at once.

Quick check· 5 min

Why does splitting work?

In the circular version, why is running the linear algorithm on the two slices sufficient?

The two cases, first taken and first not taken, are exhaustive, and in each the wrap-around constraint cannot bindThe circular constraint only matters when the list has an even lengthBecause the maximum is always achieved somewhere in the middle of the listIt is an approximation that is correct on almost all inputs

Problem· 22 min

House Robber Ii

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def linear_best(values):2 take, skip = 0, 03 for value in values:4 take, skip = skip + value, max(take, skip)5 return max(take, skip)6 7values = [1, 2, 3, 1]8print("everything: ", values, "->", linear_best(values))9print("without the first:", values[1:], "->", linear_best(values[1:]))10print("without the last: ", values[:-1], "->", linear_best(values[:-1]))