一、 只能买卖1次
https://leetcode-cn.com/explore/interview/card/bytedance/246/dynamic-programming-or-greedy/1042/
应该算典型的贪心思路。
遍历数组，把第一个设为买的价格，记为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元，经过一系列操作后，手里钱最多。那么买一次，其实是减去当前的钱，卖一次就加上当前的钱啦。
对于每一天，有三个状态，买，卖，冻结。
- 冻结：很好理解，手里的钱等于上一次卖的钱
- 买：买的前提是上一次必须处于冻结（因为不能连续买嘛），那么买完后手里当前等于冻结的钱减去当前手里钱，但是这里要考虑到一个利益最大化，即我今天如果不买，搞不好昨天买的钱还多了V （其实是考虑昨天买今天不买，今天也是出于买的状态中的）。所以这里要取一个两者的最大值。
- 卖：卖的前提是前一天是买的状态。同样也比较下昨天卖的最大值
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
