题解 | #买卖股票的最好时机(三)#

思路分析

主要思路：贪心+分治。

题目要求的是两段收益最大区间的收益之和，主要使用到的一个性质是：

第 $i$ 天对应时间的价格简记为 $p_i$ 。
假设在给定的数据范围 $[L,R)$ 内，已经找到了当前收益最大的一次买卖操作时间，买入时间记为 $i$ 、卖出时间记为 $j$ ，有 $L\le i\le j<R$ 。
则不存在 $a_i,a_j,b_i,b_j$ 满足 $a_i\le a_j<b_i\le b_j, p_j-p_i < (p_{a_j}-p_{a_i}) + (p_{b_j}-p_{b_i})$ 。

即：在范围 $[L,r)$ 内的全局最优解一定大于任意两个局部最优解之和，因此不需要去考虑重叠子的问题，直接贪心即可。

代码

主要思路：先找到全局完整区间内的最优解（26行），再在最优解所划分的左右两半区间中找到次优解（27、28行），求和（29行）。对给定区间进行求解的算法可以参考 BM80 买卖股票的最好时机(一) 解法（6-24行）的最优实现（ $O(1)$ 空间、 $O(n)$ 时间）。
总复杂度：在三次执行find中最多完整地遍历两次 prices， $O(1)$ 空间、 $O(n)$ 时间。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # write code here
        n = len(prices)

        def find(left, right):
            i_ma = i_mi = left
            r_ma = r_mi = left
            profit = 0
            for i in range(left, right):
                ma = prices[i_ma]
                mi = prices[i_mi]
                p = prices[i]
                if p >= ma:
                    i_ma = i
                    # profit = max(profit, prices[i_ma] - prices[i_mi])
                elif p < mi:
                    i_mi = i_ma = i
                if profit < prices[i_ma] - prices[i_mi]:
                    profit = prices[i_ma] - prices[i_mi]
                    r_ma, r_mi = i_ma, i_mi
                profit = max(profit, prices[i_ma] - prices[i_mi])
            print(f"find({left}, {right})", profit, r_mi, r_ma)
            return profit, r_mi, r_ma

        ans, i, j = find(0, n)
        v1, _, _ = find(0, i)
        v2, _, _ = find(j, n)
        return ans + max(v1, v2)