> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/09_dynamic_program/121.-best-time-to-buy-and-sell-stock.md).

# 121. Best Time to Buy and Sell Stock

<https://leetcode.com/problems/best-time-to-buy-and-sell-stock/>

## solution

* 贪心: 只能进行一笔买卖交易

```python
# 一次迭代过程，只记录之前出现的最低值，也计算目前出现的最大利润。两种计算非同时触发
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        low = float('inf')
        profit = 0
        for price in prices:
            if price < low:  # 可转化为 low = min(low, i), 截止到目前遇到的最低价格
                low = price
            if price - low > profit:  # 可转化为 profit = max(profit, i - low), 截止目前的最大利润
                profit = price - low
        return profit
```

时间复杂度：O(n)\
空间复杂度：O(1)

* 动态规划
  * dp含义很关键，注意`dp[i][0]`和`dp[i][1]`分布是**持有**和**不持有**股票，手里最多现金。持有可以是原来就持有，也可以是当天才买。不持有可以是一直不持有，可以是当天才卖。
  * 初始可以认为现金是0，可以初始假设了某笔钱，最后也需要减掉。然后，中间如果有亏损，本身也是负的现金

```python
# 只和过去一个时间有关的, 空间可以优化
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[0] * 2 for _ in range(len(prices))]

        dp[0][0] = -prices[0]
        dp[0][1] = 0

        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], -prices[i])  # 只进行一笔，所以买之后利润肯定是-当前价格
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])

        return dp[-1][1]
```

时间复杂度：O(n)\
空间复杂度：O(n)

## follow up-股票买卖类

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

* 可以进行无数笔交易，注意先买后卖
* 递增区间的和
* dp含义不变，只是公式有更新

```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[0] * 2 for _ in range(len(prices))]
        dp[0][0] = -prices[0]
        dp[0][1] = 0

        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
        return dp[-1][1]
```

时间复杂度：O(n)\
空间复杂度：O(n)

```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        res = 0
        for i in range(1, len(prices)):
            if prices[i] >= prices[i-1]:  # 递增区间
                res = res + prices[i] - prices[i-1]  # 和
            else:
                continue
        return res
```

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

* 最多完成两笔交易
* dp含义差不多？类似问题中，二维dp中的第二维是某种状态枚举

```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0

        dp = [[0] * 4 for _ in range(len(prices))]
        dp[0][0] = -prices[0]
        dp[0][2] = -prices[0]  # 注意第二次持有的初始化

        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], -prices[i])  # 注意和前几天的比较
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
            dp[i][2] = max(dp[i-1][2], dp[i-1][1]-prices[i])
            dp[i][3] = max(dp[i-1][3], dp[i-1][2]+prices[i])
        return max(dp[-1][1], dp[-1][3])
```

时间复杂度：O(n)\
空间复杂度：O(n), 可继续优化至O(1)

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

* 最多完成k笔交易
* 把最多完成两笔交易中的2进一步参数化

```python
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0

        dp = [[0] * (2 * k + 1) for _ in range(len(prices))]
        for j in range(1, 2 * k, 2):
            dp[0][j] = -prices[0]  # 同样注意所有奇数次持有的初始化

        for i in range(1, len(prices)):
            for j in range(0, 2 * k - 1, 2):
                dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]-prices[i])
                dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1]+prices[i])
        return dp[-1][2*k]
```

时间复杂度：O(n)\
空间复杂度：O()

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

* 含冷冻期
* 注意状态划分与转移，仍然是第二维是状态

```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0

        dp = [[0] * 4 for _ in range(len(prices))]
        dp[0][0] = -prices[0]

        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][2]-prices[i])  # hold, 之前持有或非冷冻期买入
            dp[i][1] = dp[i-1][0] + prices[i]  # sell, 前一天持有后卖出，卖出后进入的是冷冻状态，因此没有dp[i-1][1]
            dp[i][2] = max(dp[i-1][2], dp[i-1][1])  # cool, 注意该状态是冷冻或冷冻期之后可买入的状态， 因此还要和自己过去比较
        return max(dp[-1][1], dp[-1][2])
```

时间复杂度：O(n)\
空间复杂度：O()

[714. Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)

* 含交易手续费
* 和122类似，卖出时加上手续费

```python
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        if len(prices) <= 1:
            return 0

        dp = [[0] * 2 for _ in range(len(prices))]
        dp[0][0] = -prices[0]

        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
        return dp[-1][1]
```

时间复杂度：O(n)\
空间复杂度：O()