Three situations, one per day
Give each situation you can be in its own number, and let each day's numbers come from yesterday's. About 14 minutes.
Buying and selling with a rest day
You can buy a share and sell it later, as many times as you like, but only one share at a time. After you sell, you must sit out the next day before buying again. You know the price for each day in advance, and want the best total profit.
Instead of thinking about buy and sell days, think about the situation you are in at the end of each day. There are only three.
Each situation comes from yesterday
Think of each situation as a room, and each day you may walk through certain doors. Holding a share: you were already holding, or you were free and bought today. Resting: you were holding and sold today. Free: you were free already, or you were resting yesterday and the rest day is over.
For every room, keep the best profit so far. At the end, the best answer is the larger of resting and free, because ending while still holding a share never beats selling it.
hold = max(hold, free - price) # keep holding, or buy
Day 1, price 2. Buying costs 2, so holding is worth −2. You can't have sold anything yet, and being free is worth 0.
You sell a share on Monday, and the rule is one rest day after a sale. What is the earliest day you can buy again?
- AWednesday
- BTuesday
- CMonday, straight away
Show the answer
Wednesday. Tuesday is the rest day, so Wednesday is the first day you are free to buy.
Stock with a rest day
You are given the price of a share on each day. You may buy and sell as many times as you like, but hold at most one share at a time, and after selling you must skip the next day before buying again. Return the largest total profit.
prices = [1, 2, 3, 0, 2] → 3
1 ≤ days ≤ 300 · 1 ≤ price ≤ 1,000