Start learning free

LESSON 532 OF 677 · DYNAMIC PROGRAMMING

Best Time to Buy and Sell Stock with Cooldown

Practice O(n)

You get an array prices. prices[i] is what one share costs on day i.

Return the most profit you can make by buying and selling.

Each day you can buy one share, sell your share, or do nothing. You can hold only one share at a time. You can buy and sell as many times as you like.

After a sale you must rest for one day. So you can't buy on the day right after you sell.

 

Example 1:

Input: prices = [3, 5, 1, 4]
Output: 3
Explanation: Buy at 1 on day 2.
Sell at 4 on day 3.
That earns 4 - 1 = 3.
Buying at 3 and selling at 5 earns only 2.
After that sale, day 2 is a rest day.
So the share at 1 could not be bought.

Example 2:

Input: prices = [2, 6, 5, 1, 7]
Output: 10
Explanation: Buy at 2 on day 0 and sell at 6 on day 1.
That earns 4.
Day 2 is the rest day.
Buy at 1 on day 3 and sell at 7 on day 4.
That earns 6.
In total, 4 + 6 = 10.

Example 3:

Input: prices = [9, 7, 4]
Output: 0
Explanation: The price only goes down.
Every sale would lose money.
So the best plan is to never buy.

 

Constraints:

  • 1 to 5,000 days.
  • Each price is a whole number from 0 to 1,000.

Note:

Your solution should run in O(n) time and use O(1) extra space.



Trying every plan of buys and sells is far too slow. Go day by day instead. At the end of a day you are in one of three states:
  • holding: you own a share;
  • sold: you sold your share today;
  • resting: you own nothing and did not sell today.
Keep the best profit for each state. A purchase counts as minus its price.

Each state comes from yesterday's states:
  • sold: sell today the share you held yesterday;
  • holding: keep yesterday's share, or buy today after a resting day;
  • resting: rest again, or rest the day after a sale.
A purchase never starts from sold. That is the rest day. The answer is the better of sold and resting on the last day.

Each day takes a few steps: O(n) time. Only three running numbers are kept: O(1) extra space.
STEP 1 OF 9
    Ctrl + Enter to check