Iteration

Case Analysis Problems

Lesson

In this kind of problem, you need to break the problem down into a few cases in order to make progress.

Problem: You're a landlord, and you want to buy the most valuable houses in a neighborhood. Due to regulations, you're not allowed to buy 2 houses that are next to each other. All the houses are on a single loop.

Given the price of each house prices, return the maximum value of houses that you can buy.

image

Example:

prices = [5, 5, 5]=> returns 5\notag \large \texttt{prices = [5, 5, 5]}\\ \large \texttt{=> returns 5}

Explanation: There are 3 houses in the loop, each with price 5. You can only buy one of them. Any other house you buy would be next to that house, which is against the rules.

You can assume the loop has at least 2 houses in it.

Hint: You should solve the original Richest Landlord problem before solving this problem.

First Few Test Cases:

1. Suppose the landlord should buy the first house. Then we could find his max profit by considering the best way to buy houses 0...n-2.

2. Suppose the landlord shouldn't buy the first house. Then we could find his max profit by considering the best way to buy houses 1...n-1.

One of these cases will definitely be true, since the landlord either should or shouldn't buy the first house. So we can just solve these two cases using the original algorithm we came up with in Richest Landlord, and take the max of these two cases.

Time Complexity O(n)O(n). We iterate through all nn houses twice.

Space Complexity O(1)O(1)

Mark as Completed:
Submits:
richestLandlordLoop
Test your code to get an output here!
richestLandlordLoop(
)
Test your code to get an output here!