买卖股票的最佳时机 123

一、 只能买卖1次

https://leetcode-cn.com/explore/interview/card/bytedance/246/dynamic-programming-or-greedy/1042/

image.png

应该算典型的贪心思路。
遍历数组，把第一个设为买的价格，记为buy
对于数组每个数，如果当前价格小于buy，则更新buy，因为这时候肯定不会卖出的，只考虑用更低买入
如果当前价格大于buy，说明可以卖了，这时候更新下利润的最大值就行了，最后返回利润最大值。

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices or len(prices)<2:
            return 0
        buy = prices[0]
        result = 0
        for i in range(1,len(prices)):
            if prices[i]<buy:
                buy = prices[i]
            else:
                result = max(result,prices[i]-buy)

        return result
        

二、 可以买卖多次

也可以用贪心的策略，但是目标要改下，只要下次的价格，比前一个卖出的钱少，就把前面卖掉。然后从这一刻开始买。注意sell可能开始不存在，代码需要判断下是否存在，对不同的情况做不同的判断
代码如下：

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices or len(prices)<2:
            return 0
        buy = prices[0]
        sell = None
        result = 0
        for i in range(1,len(prices)):
            # 这里要看下sell到底存在不，不存在的时候，只要更新下buy和sell
            if not sell:
                if prices[i]<=buy:
                    buy = prices[i]
                else:
                    sell = prices[i]
            else:
                if prices[i]<sell:
                    result = result + sell-buy
                    buy = prices[i]
                    sell = None
                else:
                    sell = prices[i]
                    
        if sell and sell-buy>0:
            result = result + sell-buy
        return result

看网上还有一种大神的思路，直接吧前面一个减去后面，只要大于0，全部收益加起来！

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        rst = 0
        t = [prices[i+1] - prices[i] for i in range(len(prices)-1)]
        for item in t:
            if item > 0:
                rst += item
        return rst

可以买卖多次，加上冷冻期，如果卖了，下一条不能买

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

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:

输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

这样的话，不能用贪心去解决了。只能考虑动态规划。
动态规划就是根据状态找规律。。。
我们重新审视下这个关系，最后要求的是利润最大，即开始手上0元，经过一系列操作后，手里钱最多。那么买一次，其实是减去当前的钱，卖一次就加上当前的钱啦。
对于每一天，有三个状态，买，卖，冻结。

1. 冻结：很好理解，手里的钱等于上一次卖的钱
2. 买：买的前提是上一次必须处于冻结（因为不能连续买嘛），那么买完后手里当前等于冻结的钱减去当前手里钱，但是这里要考虑到一个利益最大化，即我今天如果不买，搞不好昨天买的钱还多了^V （其实是考虑昨天买今天不买，今天也是出于买的状态中的）。所以这里要取一个两者的最大值。
3. 卖：卖的前提是前一天是买的状态。同样也比较下昨天卖的最大值

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices or len(prices)<2:
            return 0
        buy = -prices[0]
        sell = 0
        cold = 0
        for i in prices[1:]:
            # 记录昨天的状态
            cold_pre = cold
            sell_pre = sell
            buy_pre = buy
            # 更新今天的状态
            cold = sell_pre
            buy = max(buy_pre,cold_pre-i)
            sell = max(sell_pre,buy_pre+i)
        return sell