python实现leetcode之123. 买卖股票的最佳时机

解题思路

三遍扫描，时间复杂度N，空间复杂度也是N
第一遍从左到右，计算到目前为止最大的利润
第二遍从右到左，计算从目前开始最大的利润
第三遍并行扫描前两步的结果然后返回最大和

123. 买卖股票的最佳时机 III

代码

class Solution(object):
    def maxProfit(self, prices):
        N = len(prices)
        if not N: return 0
        in_order = []  # 到目前为止最大的利润
        max_value, min_index = 0, 0
        for idx in range(N):
            p = prices[idx]
            if p < prices[min_index]: min_index = idx
            if p - prices[min_index] > max_value: max_value = p - prices[min_index]
            in_order.append(max_value)
        
        un_order = []  # 从目前开始最大的利润
        max_value, max_index = 0, N-1
        for idx in range(N):
            ridx = N-1-idx
            p = prices[ridx]
            if p > prices[max_index]: max_index = ridx
            if prices[max_index] - p > max_value: max_value = prices[max_index] - p
            un_order.insert(0, max_value)
        return max([x + y for x, y in zip(in_order, un_order)])