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

水深无声 2022-04-11 11:17 158阅读 0赞

**【前言】**

python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/details/89470836][https_blog.csdn.net_weixin_40449300_article_details_89470836]

github链接：[https://github.com/Teingi/test][https_github.com_Teingi_test]

**【正文】**

给定一个数组，它的第* i* 个元素是一支给定的股票在第 *i *天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 *两笔 *交易。

**注意:** 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

**示例 1:**

输入: [3,3,5,0,0,3,1,4]
    输出: 6
    解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
         随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

**示例 2:**

输入: [1,2,3,4,5]
    输出: 4
    解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
         注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
         因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

**示例 3:**

输入: [7,6,4,3,1] 
    输出: 0 
    解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

思路：考虑到最多只能交易两次，我们先考虑交易一次，得到当次最大利润，再讨论第二次交易的情况。对于prices数组list，不妨设该次开始交易的指针为begin，卖出当前股票时指针为stop，那么整个list就被begin、stop指针分为3个part，其中我们在第一次交易时已求得part\_2最大利润值。对于第二次交易，有三种情况，即可能处于part\_1或part\_2或part\_3中。

（i）如果是part\_1，则返回part\_1及part\_2最大利润的和；   
（ii）如果是part\_2，类似’N’型的折线，结果应当是第一次交易的最大利润加上两次极值转折跌价的差值   
而两次极值转折跌价的差值实际是part\_2倒序的最大利润值，也就是代码中Solve函数参数 t = -1 的情况；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70][]  
（iii）如果是part\_3，则返回part\_2及part\_3最大利润的和。   
最后在选取上述三种情况的最大值。

相比 I 题，我们只需在求解最大利润的同时找到其开始买入（begin）以及卖出股票（stop）的list指针，在分别算出3个part的最大利润，最后返回题设的最大利润。

class Solution:
        """
        @param prices: Given an integer array
        @return: Maximum profit
        """
        def Solve(self,part, t):
            """
            求一次交易的最大利润函数
            """
            if t == -1:
                part = part[::-1]
            if part is None or len(part) < 2:
                return 0
            Begin_value = part[0]
            result = 0
            for p in part:
                result = max(result, p-Begin_value)
                Begin_value = min(Begin_value, p)
            return result
        
        
        def maxProfit(self, prices):
            # write your code here
            if prices is None or len(prices) < 2:
                return 0
            begin, index, stop = 0, 0, 1    #开始买入指针，临时指针，结束卖出指针
            Sum, Max = 0, 0
            for i in range(len(prices)-1):
                Sum += prices[i+1]-prices[i]
                if Sum > Max:
                    Max = Sum
                    stop = i + 1
                    begin = index
                Sum = max(0, Sum)
                if Sum == 0:
                    index = i + 1
            part_1 = Max + self.Solve(prices[:begin], 1)
            part_2 = Max + self.Solve(prices[begin:stop+1], -1)if Max > 0 else 0
            part_3 = Max + self.Solve(prices[stop+1:], 1)
            #part_2中的判断语句是因为可能出现part_2最大利润Max为0，即递减数组，而第二次交易又在此part，第二次的最大利润>0,矛盾。
            return max(part_1, part_2, part_3)

[https_blog.csdn.net_weixin_40449300_article_details_89470836]: https://blog.csdn.net/weixin_40449300/article/details/89470836
[https_github.com_Teingi_test]: https://github.com/Teingi/test
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDQ0OTMwMA_size_16_color_FFFFFF_t_70]: /images/20220411/44f6012eb9274cc6bcc04826222d6993.png