leetcode123.买股票的最佳时机3

只能买卖两次

1.二分法，超时
class Solution:
    def max_one_profit(self,prices):
        if not prices:
            return 0
        
        max_profit=0
        min_price=prices[0]
        for i in range(1,len(prices)):
            if prices[i]<min_price:
                min_price=prices[i]
            if prices[i]-min_price>max_profit:
                max_profit=prices[i]-min_price
        return max_profit
    
    def maxProfit(self, prices: List[int]) -> int:
        max_profit=0
        for i in range(len(prices)):
            left=prices[:i]
            right=prices[i:]
            max_p1=self.max_one_profit(left)
            max_p2=self.max_one_profit(right)
            if max_p1+max_p2>max_profit:
                max_profit=max_p1+max_p2
        return max_profit

2.动态规划

leetcode123.买股票的最佳时机3

原文：https://www.cnblogs.com/liguitar/p/11521669.html