### Introduction

In this article I will try to solve **Best Time to Buy and Sell Stock** series problem, including **Best Time to Buy and Sell Stock I, II, III, IV** and **with Cooldown.** Most of them are solved by **dynamic programming** and I will focus on construct transition equation and dimension reduction.

### Description

The description of **Best Time to Buy and Sell Stock I** is:

Say you have an array for which the $i^{th}$ element is the price of a given stock on day $i$.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example:

1 | Input: [7,1,5,3,6,4] |

### Solution of Problem I

A simple idea is using `dp[i]`

as **the most profit buying in $i^{th}$ day.** Then the transition equation will be `dp[i] = max(prices[j] - prices[i]) for all j > i`

and the soluton is `max(dp)`

. It will be an $O(n^2)$ algorithm. But there is a waste of computation in this method. We suppose $j$ is the specific day that `dp[i] = prices[j] - prices[i]`

, then if there is a $k$ makes $dp[k] < dp[i]$ and $k > i$, then we have

So the soluton won’t be `dp[i]`

. Under this circumstance, we cam simplify our algorithm by **always searching lower price day as buying day**, record the current price minus buying day price(**the lowest price before/on current $i^{th}$ day**) and generate a sequence of profit. The `profit[i]`

means the difference between $i^{th}$ day price and the lowest price before/on $i^{th}$ day. So `max(profit)`

will be the solution. By doing so, we reduce the method into $O(n)$ time. Here is the cpp code.

1 | class Solution { |

### Solution of Problem II

In problem II, we have not the transaction number limitation, **we can buy/sell any times.** When we try to using the `dp[i]`

as above, we find that it’s hard to build a transition equation because we don’t know how many transaction times there will be. We have to change our state description. We have **only three actions** in a day, buying, selling and doing nothing, so we can use two states to describe a day, i.e. **a day with stock** and **a day without stock**. Let `nohold[i]`

be the maximal profit when we have not stock in $i^{th}$ day, `hold[i]`

be the maximal profit when we have stock. Then the transition equation will be

1 | hold[i] = max(hold[i-1], nohold[i-1] - prices[i]); |

That simply means if we have stock in $i^{th}$ day, the stock can be bought today or we already have it yesterday and if we have stock in $i^{th}$ day, the stock can be sold today or yesterday or before. By this equation, we can solve this problem in one pass. Don’t forget the initialization `nohold[0] = -prices[0]`

.

1 | class Solution { |

There is another solution **do not use DP.** A trivial idea is that we buy all the stock at the begin of an **increasing line** and sell it at the end of line, we can get the most profit.

1 | class Solution { |

### Soluton of III & IV

Problem III is a special case of Problem IV, so we just introduce Problem IV. In Problem IV, we have a limitation that **we can only buy $k$ times($k$ is given).** It can be solved simply like the DP algorithm of Problem II. We can use similar state description and just increase a dimension of **transaction times.** Let `hold[i][j]`

as the maximal profit when we have stock and $j$ transitions on $i^{th}$ day and `nohold[i][j]`

as the maximal profit when we have no stock and have $j$ transitions on $i^{th}$ day. Also like Problem II, the transition equation can be written as

1 | hold[i][j] = max(hold[i-1][j], nohold[i-1][j-1] - prices[i]); |

The solution will be `nohold[n-1][k-1]`

. What need to be mentioned is that **we counting transaction by counting buying numbers but not selling.** Then it’s a one-pass method.

1 | class Solution { |

But the code **did not pass!** We got a **Memory Limit Exceeded.** So I start to reduce the dimension of the equation. Obviously, both `hold[i][j]`

and `nohold[i][j]`

have only relationship with `hold[i-1][*]`

and `nohold[i-1][*]`

. So we can just reduce it as

1 | hold[j] = max(hold[j], nohold[j-1] - prices[i]); |

Also, using a **sentinel $0$ in nohold[j]** can make code looks better(reduce the number of $if$). So we get the code like this.

1 | class Solution { |

~Ok, we have already solved it!~ Wait, it’s still **Memory Limit Exceeded!** But why? If we consider a super large $k$ that the limitation is meaningless to the problem, the problem **reduces into Problem II.** But the time complexity of our solution will still be $O(k*\dot n)$, which is a super large number especially comparing with $O(n)$ solution in Problem II. We can solve this by a simple $if$ sentence.

1 | if(k > n/2){ |

And here is the whole program of Problem IV.

1 | class Solution { |

### Solution of Problem **with Cooldown**

Cooldown means we have to ~have relax and take a coffee~ the day after selling. **Buying the day after a selling is not allowed.** That means our states description above can not be used again…Of course not! We can just do a little modification, adding a new vector called `cooldown[i]`

means the maximal profit when we **just sell or do nothing** on the $i^{th}$ day. We have `have_stock[i]`

and `have_no_stock[i]`

as above. We can find the transition of cooldown like `cooldown[i] = max(hold_no_stock[i-1], hold_stock[i-1] + prices[i])`

which means today we sell the stock or do nothing. The transition of hold_stock is still `hold_stock[i] = max(hold_stock[i-1], hold_no_stock[i-1] - prices[i])`

because cooldown doesn’t influence buying. Finally the transition equation pf `hold_no_stock[i]`

can be `hold_no_stock[i] = max(hold_no_stock[i-1], cooldown[i-1])`

, meaning that today is a **cooldown day or no stock day.** Combine them together we have_stock

1 | hold_no_stock[i] = max(hold_no_stock[i-1], cooldown[i-1]); |

Don’t forget the initialization `hold_stock[0] = -prices[0]; cooldown[0] = INT_MIN;`

. It’s also a $O(n)$ one-pass method now. In conclusion, all these kind of problem can be solved by dynamic programming idea and the basic idea is to form transition equation. **The number of variables or the number of dimensions are equivalent** in constructing equation. So if you have not idea how to form the equation, including the variable number of state will be a good choice.

1 | class Solution { |