Vinyl Flip Profit
Medium · dynamic programming
A record dealer follows the price of one rare vinyl pressing. The list prices gives its price on each day, in order. The dealer can buy copies and sell them again, but with these rules:
- at most one copy can be held at a time, so a copy must be sold before another is bought;
- a copy is bought on one day and sold on a later day;
- every sale costs a flat
fee, paid on top of the price; - after a sale, the dealer needs a break of
restfull days before buying again. If a copy is sold on dayd, the next purchase can happen on dayd + rest + 1at the earliest.
Each day the dealer can buy, sell or do nothing. Return the largest total profit that can be made, counting prices and fees. If no plan makes money, return 0.
Examples
Example 1
Input: prices = [1, 5, 2, 8], fee = 1, rest = 0
Output: 8
Buy at 1 and sell at 5 (profit 4 - 1 = 3), then buy at 2 and sell at 8 (profit 6 - 1 = 5). Total 8.
Example 2
Input: prices = [1, 5, 2, 8], fee = 1, rest = 1
Output: 6
Selling at 5 on day 1 means no purchase before day 3, when the price is already 8. The best plan is to buy at 1 and sell at 8 for 7 - 1 = 6.
Example 3
Input: prices = [4, 3], fee = 0, rest = 2
Output: 0
The price only falls, so the best plan is not to trade.
Constraints
- 1 <= len(prices) <= 10^5
- 1 <= prices[i] <= 10^4
- 0 <= fee <= 10^4
- 0 <= rest <= 10^5