LeetCode-123 买股票的最佳时机 3（python）

题目链接：123 买股票的最佳时机 3

 分析

这个相比于前两题就要花点心思了，看题目原话

“你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）”，这个参考上篇博客里的1, 2, 3这个例子，

执行过程依然是

第一天买入，第二天卖出，收入为1，然后第二天再买入，第三天再卖出，收入为1，累计收入为2，（交易两次）。

等同于第一天买入，第三天卖出（交易一次）。没规定必须交易几次。

但是两笔交易一定有先后。

在[1, 2, ...... n-1, n] 中可把两次交易分为[1, 2, ...... i] 和 [i, ...... n-1, n]，这个分解过程是122中的思想，

接着分别计算[1, 2, ...... i] 和  [i, ...... n-1, n] 中的最大利润 f[i] 和 g[i]，计算方法在121中得以体现

我们最后就是取出 max(f[i], g[i]) 就可以了。

 代码

def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""len_prices = len(prices)if len_prices < 2:return 0# 用来记录不同区间里的最大利润f = [0] * len_pricesg = [0] * len_prices  # 计算原则就是121的解minf = prices[0]for i in range(1, len_prices):minf = min(minf, prices[i])f[i] = max(f[i-1], prices[i] - minf)maxg = prices[len_prices-1]for i in range(len_prices-1)[::-1]:maxg = max(maxg, prices[i])g[i] = max(g[i], maxg - prices[i])# 取其中最大值maxprofit = 0for i in range(len_prices):maxprofit = max(maxprofit, f[i] + g[i])return maxprofit

而且这个时间复杂度和空间复杂度都为O(n)

 刷题GitHub：https://github.com/letterbeezps/leetcode-algorithm 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！