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

题目链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
难度：中等

描述：
给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。
在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

题解

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        # r[i][0]：第i天未持有股票所获得的最大利润
        # r[i][1]：第i天持有股票所获得的最大利润
        r = [[0] * 2 for _ in range(n)]
        r[0][0] = 0
        r[0][1] = r[0][0] - prices[0]
        for i in range(1, n):
            # 要么前一天手上就没有股票，要么今天把股票卖掉
            r[i][0] = max(r[i-1][0], r[i-1][1] + prices[i])
            # 要么前一天手上就有股票，要么今天刚买进
            r[i][1] = max(r[i-1][1], r[i-1][0] - prices[i])
        # 显然卖掉股票利润更高
        return r[n-1][0]

但这题用贪心算法更简单：一旦prices[i] > prices[i-1]，那么就买入第i-1天的股票，卖出第i天的股票。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ret = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                ret += prices[i] - prices[i-1]
        return ret