# 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()


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://longxingtan.gitbook.io/mle-interview/01_leetcode/09_dynamic_program/121.-best-time-to-buy-and-sell-stock.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.