This series of **Buy and Sell Stock I~VI** on Leetcode is a great practice for Dynamic Programming – State Machine. Therefore I prepared blogs for each of them and hopefully it would help you to understand them better. You can find the relations of them at the bottom and feel free to leave any comments.

- [Leetcode]121. Best Time to Buy and Sell Stock
- [Leetcode]122. Best Time to Buy and Sell Stock II
- [Leetcode]123. Best Time to Buy and Sell Stock III
- [Leetcode]188. Best Time to Buy and Sell Stock IV
- [Leetcode]309. Best Time to Buy and Sell Stock with Cooldown
- [Leetcode]714. Best Time to Buy and Sell Stock with Transaction Fee

Say you have an array for which thei^{th}element is the price of a given stock on dayi. 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.

#### From brute force O(n^2) to O(n)

The most straightforward approach would be: for each day `i`

, we would find the largest profit we could make if we buy the stock on day `j (j<i)`

with the lowest price and sell it on day `i`

. To find the lowest price that we can get, we could scan the stock `prices[0...i]`

. This would lead to O(n^2) time complexity, and if we could record the lowest price and update it during the iteration, we can get a O(n) solution.

```
class Solution:
def maxProfit(self, prices: List[int]) -> int:
total = 0
low = float('inf')
for p in prices:
low = min(low,p)
total = max(total,p-low)
return total
```

#### State machine – 1-D Dynamic programming

There are two states in this context: `hold`

holds stock in hand while `cash`

has no stock in hand. The way they can transit from one to the other is illustrated as below and one thing to notice is that, as we can only do 1 transaction, therefore there’s no path from `cash`

to `hold`

as we cannot rebuy the stock once we did.

```
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
n = len(prices)
hold,cash = [0]*n,[0]*n
hold[0] = -prices[0]
for i in range(1,n):
hold[i] = max(hold[i-1],-prices[i])
cash[i] = max(cash[i-1],hold[i-1]+prices[i])
return cash[-1]
```

`hold[i]`

means the largest profit we could make if we hold the stock on day`i`

.`sold[i]`

means the largest profit we could make if we do not hold the stock on day`i`

.

Moreover, we can further optimise it from O(n) space complexity to O(1). Noticing that `hold[i]`

is only affected by `hold[i-1]`

and `cash[i]`

is only affected by `cash[i-1]`

and `hold[i-1]`

, instead of using arrays, we could use integers to record and update `cash`

and `hold`

if we update `cash`

first.

```
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
hold = -prices[0]
cash = 0
for price in prices[1:]:
cash = max(cash,hold+price)
hold = max(hold,-price)
return cash
```

#### State machine – 2-D Dynamic programming

This 2D DP also follows the intuition of the state machine, yet it maintains the constraint of at most 1 transaction by using a 2-dimensional array. Actually this is a special case of the constraint that there are at most K transactions when `K=1`

, therefore more details about this approach is explained in 123. Best Time to Buy and Sell Stock III (Hard).

```
class Solution:
def maxProfit(self, prices: List[int]) -> int:
K = 1
if len(prices) < 2:
return 0
dp = [0] * (K+1)
low = [prices[0]] * (K+1)
for i in range(1,len(prices)):
for k in range(1,K+1):
low[k] = min(low[k],prices[i]-dp[k-1])
dp[k] = max(dp[k],prices[i]-low[k])
return dp[-1]
```