# 122. 买卖股票的最佳时机 II

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

## 解法一：一次遍历

观察可知，一次遍历，累加每个上坡的长度（峰值减去谷值）即可，注意谷在峰之前，每次与**前一位**比较找谷和峰。

```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        i, peak, valley, max_profit = 1, 0, 0, 0    #i从1开始
        while i < len(prices):
            while i < len(prices) and prices[i] <= prices[i-1]:
                i += 1
            valley = prices[i-1]    #先找谷值
            while i < len(prices) and prices[i] >= prices[i-1]:
                i += 1
            peak = prices[i-1]    #再找峰值
            max_profit += peak - valley     #累加差值
        return max_profit
```

或者与**后一位**比较：

```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        i, peak, valley, max_profit = 0, 0, 0, 0    #i从0开始
        while i < len(prices)-1:
            while i < len(prices)-1 and prices[i+1] <= prices[i]:
                i += 1
            valley = prices[i]    
            while i < len(prices)-1 and prices[i+1] >= prices[i]:
                i += 1
            peak = prices[i]
            max_profit += peak - valley
        return max_profit
```

## 解法二：状态机dp

参照状态机模型，如果 k 为正无穷，可以认为 k 和 k - 1 是一样的。状态方程变为

```
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
            = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])
```

我们发现数组中的 k 已经不会改变了，也就是说不需要记录 k 这个状态了：

```
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])
```

直接出代码：

```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0:
            return 0
        dp = [[0] * 2 for _ in range(n + 1)] 
        for i in range(n+1):
            if i == 0:
                dp[i][0] = 0
                dp[i][1] = -sys.maxsize
                continue
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1])
        return dp[n][0]
```


---

# 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://cai-sen-se.gitbook.io/leetcode/1-200/122.-mai-mai-gu-piao-de-zui-jia-shi-ji-ii.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.