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

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

解法一：一次遍历

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

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

或者与后一位比较：

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

直接出代码：

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]