LeetCode 122. 买卖股票的最佳时机 II（Python3）
思路：贪心
由于可以无限次交易，只要第二天价格比第一天高，就可以在前一天买入、第二天卖出，赚取差价。
把所有相邻两天的正收益累加起来，就是最大利润。
例如：[7,1,5,3,6,4]
· 1 -> 5 赚 4
· 3 -> 6 赚 3
· 总利润 7
Python3 实现（贪心）
classSolution:defmaxProfit(self,prices:List[int])->int:profit=0foriinrange(1,len(prices)):ifprices[i]>prices[i-1]:profit+=prices[i]-prices[i-1]returnprofitPython3 实现（动态规划）
用 dp0 表示当天不持股的最大利润，dp1 表示当天持股的最大利润。
classSolution:defmaxProfit(self,prices:List[int])->int:# dp0: 不持股，dp1: 持股dp0=0dp1=-prices[0]foriinrange(1,len(prices)):new_dp0=max(dp0,dp1+prices[i])new_dp1=max(dp1,dp0-prices[i])dp0,dp1=new_dp0,new_dp1returndp0关键点
- 贪心法：每一段上涨都拆成每天的正收益，累加即可。
- 动态规划：状态转移：
· 不持股：max(昨天不持股, 昨天持股 + 今天价格)
· 持股：max(昨天持股, 昨天不持股 - 今天价格) - 无限次交易：买入时不需要考虑之前是否卖出，因此 dp0 - prices[i] 可以直接用。
复杂度
· 时间：O(n)，遍历一次。
· 空间：贪心法 O(1)；DP 法 O(1)。
测试用例
maxProfit([7,1,5,3,6,4])# 7maxProfit([1,2,3,4,5])# 4maxProfit([7,6,4,3,1])# 0
