# -*- coding:utf-8 -*-

class Stock:
    def data(self,i,j,prices):
        min_num=float("inf")
        max_num=0
        x=i
        while x!=j:
            if prices[x]<min_num:
                min_num=prices[x]
            elif prices[x]-min_num>max_num:
                max_num=prices[x]-min_num
            x+=1
        return max_num
    def maxProfit(self, prices, n):
        # write code here
        max_n=0
        for i in range(n):
            num1=self.data(0,i,prices)
            num2=self.data(i,n,prices)
            if num2+num1>max_n:
                max_n=num2+num1
        return max_n
参考大佬的思路

class Stock:
    def maxProfit(self, prices, n):
        buy1,sell1,buy2,sell2=[],[],[],[]#分别保存每次交易后的最大收益
        for i in range(n):
            buy1.append(0-prices[i])
            if i>0:
                sell1.append(max(buy1[:i])+prices[i])
            if i>1:
                buy2.append(max(sell1[:i])-prices[i])
            if i>2:
                sell2.append(max(buy2[:i])+prices[i])
        return max(max(sell1),max(sell2))

leetcode上的原题 ，python解法如下

class Stock:
    def maxProfit(self, prices, n):
        if not prices: return 0
        left, right = [], []
        minLeft, cur = prices[0], 0
        for i, v in enumerate(prices):
            cur = max(v - minLeft, cur)
            left.append(cur)
            minLeft = min(minLeft, v)
        maxRight, cur = prices[-1], 0
        for i, v in enumerate(prices[::-1]):
            cur = max(maxRight - v, cur)
            right.insert(0, cur)
            maxRight = max(maxRight, v)
        return max(map(lambda c: left[c] + right[c], range(len(prices))))

更简单的解法 ：

class Stock:
    def maxProfit(self, prices, n):
        buy1, buy2, sell1, sell2 = -999999999, -9999999999, 0, 0
        for x in prices:
            sell2 = max(sell2, buy2 + x)
            buy2 = max(buy2, sell1 - x)
            sell1 = max(sell1, buy1 + x)
            buy1 = max(buy1, -x)
        return sell2

两种解法都测试通过。。时间复杂度均为O(n)

class Stock:
    def maxProfit(self, prices, n):
        if n<2:
            return 0
        # left[k]=price[:k+1]'s max pj-pi(j>i)
        # right[k]=price[k:]'s max pj-pi(j>i)
        left = [0 for i in range(n)]
        for k in range(1,n):  #compute left[k]
            tmp = prices[k]-min(prices[:k])
            left[k] = max(tmp, left[k-1])
        right = [0 for i in range(n)]
        for k in range(n-2,-1,-1):  #compute right[k]
            tmp = max(prices[k+1:])-prices[k]
            right[k] = max(tmp, right[k+1])
            
        # find the best place to split price and get max r[k] = left[k]+right[k+1]
        best = 0
        for i in range(n-1):
            best = max(left[i]+right[i+1], best)
        return best