6.8 股票交易

# 6.8 股票交易

`股票交易`类问题通常可以用动态规划来解决。对于稍微复杂一些的股票交易类问题，比如需要冷却时间或者交易费用，则可以用通过动态规划实现的`状态机`来解决。

## [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)

### 题目描述

给定一段时间内每天某只股票的固定价格，已知你只可以买卖各一次，求最大的收益。

### 输入输出样例

输入一个一维整数数组，表示每天的股票价格；输出一个整数，表示最大的收益。

```
Input: [7,1,5,3,6,4]
Output: 5
```

在这个样例中，最大的利润为在第二天价格为 1 时买入，在第五天价格为 6 时卖出。

### 题解

我们可以遍历一遍数组，在每一个位置 i 时，记录 i 位置之前所有价格中的最低价格，然后将当前的价格作为售出价格，查看当前收益是不是最大收益即可。注意本题中以及之后题目中的buy 和 sell 表示买卖操作时，用户账户的收益。因此买时为负，卖时为正。

```py
def maxProfit(prices: List[int]) -> int:
    buy, sell = -sys.maxsize, 0
    for price in prices:
        buy = max(buy, -price)
        sell = max(sell, buy + price)
    return sell
```

## [188. Best Time to Buy and Sell Stock IV](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/)

### 题目描述

给定一段时间内每天某只股票的固定价格，已知你只可以买卖各 $$k$$ 次，且每次只能拥有一支股票，求最大的收益。

### 输入输出样例

输入一个一维整数数组`prices`，表示每天的股票价格；以及一个整数$$k$$，表示可以买卖的次数 。输出一个整数，表示最大的收益。

```
Input: [3,2,6,5,0,3], k = 2
Output: 7
```

在这个样例中，最大的利润为在第二天价格为 2 时买入，在第三天价格为 6 时卖出；再在第五天价格为 0 时买入，在第六天价格为 3 时卖出。

### 题解

类似地，我们可以建立两个动态规划数组 buy 和 sell，对于每天的股票价格，buy 和sell，分别表示持有股票和不持有股票的最大利润

```py
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        buy = [-inf] * (k + 1)
        sell = [0] * (k + 1)
        for i in range(n):
            for j in range(1, k + 1):
                buy[j] = max(buy[j], sell[j - 1] - prices[i])
                sell[j] = max(sell[j], buy[j] + prices[i])
        return sell[k]
```

## [309. Best Time to Buy and Sell Stock with Cooldown](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)

### 题目描述

给定一段时间内每天某只股票的固定价格，已知每次卖出之后必须冷却一天，且每次只能拥有一支股票，求最大的收益。

### 输入输出样例

输入一个一维整数数组，表示每天的股票价格；输出一个整数，表示最大的收益。

```
Input: [1,2,3,0,2]
Output: 3
```

在这个样例中，最大的利润获取操作是买入、卖出、冷却、买入、卖出。

### 题解

我们可以使用状态机来解决这类复杂的状态转移问题，通过建立多个状态以及它们的转移方式，我们可以很容易地推导出各个状态的转移方程。如图所示，我们可以建立四个状态来表示带有冷却的股票交易，以及它们的之间的转移方式。
buy, sell, s1, s2 是四个长度为 n 的数组，分别用于记录在每一天的四种状态下的最大利润：
buy[i]：表示在第 i 天买入股票时的最大利润。
sell[i]：表示在第 i 天卖出股票时的最大利润。
s1[i]：表示在第 i 天持有股票时的最大利润。
s2[i]：表示在第 i 天不持有股票且不处于冷冻期时的最大利润。

```py
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy, sell, s1, s2 = [0] *n, [0] *n, [0] *n, [0] *n
        # buy 买入， sell 卖出, s1 持有, s2 不持有且不冷却
        s1[0] = buy[0] = -prices[0]
        sell[0] = s2[0] = 0
        for i in range(1,n):
            buy[i] = s2[i-1] - prices[i]
            s1[i] = max(buy[i-1], s1[i-1])
            sell[i] = max(buy[i-1], s1[i-1]) +prices[i]
            s2[i] = max(s2[i-1], sell[i-1])
        return max(sell[n-1], s2[n-1])
```