求时间复杂度为Θ(nlogn)的股票最大利润Divide and Conquer算法

首先明确问题：给定数组，找到满足j > i的最大差值A[j] - A[i]（即低买高卖的最大利润，不可回溯时间）。你当前的分治代码复杂度为Θ(n)，是因为合并步骤仅做了常数时间的索引比较，没有处理跨区间的核心情况，也未让合并环节的时间复杂度拉到Θ(n)。要实现Θ(nlogn)的分治版本，我们需要调整合并逻辑，让每次递归的合并步骤耗时Θ(n)，这样递归式变为T(n) = 2T(n/2) + Θ(n)，根据主定理，总复杂度即为Θ(nlogn)。

算法思路 #

分治的核心是覆盖三种可能的最大利润场景：

1. 最大利润完全来自左子区间（low到middle）
2. 最大利润完全来自右子区间（middle+1到high）
3. 最大利润来自跨区间组合：左子区间的最小元素（i在左）、右子区间的最大元素（j在右）的差值

为了实现Θ(nlogn)的复杂度，我们在合并阶段不依赖递归维护的极值信息，而是主动遍历左右子区间找极值，让合并步骤的时间复杂度达到Θ(n)。

代码实现 #

def find_max_profit_divide_conquer(A, low, high):
    # 基准情况：区间无法满足j>i，返回无效利润和索引
    if low >= high:
        return -float('inf'), -1, -1
    
    middle = (low + high) // 2
    # 递归求解左右子区间的最优解
    left_profit, left_i, left_j = find_max_profit_divide_conquer(A, low, middle)
    right_profit, right_i, right_j = find_max_profit_divide_conquer(A, middle + 1, high)
    
    # 合并步骤1：遍历左半区找最小元素的索引
    min_left_val = A[low]
    min_left_idx = low
    for idx in range(low, middle + 1):
        if A[idx] < min_left_val:
            min_left_val = A[idx]
            min_left_idx = idx
    
    # 合并步骤2：遍历右半区找最大元素的索引
    max_right_val = A[middle+1]
    max_right_idx = middle+1
    for idx in range(middle + 1, high + 1):
        if A[idx] > max_right_val:
            max_right_val = A[idx]
            max_right_idx = idx
    
    # 计算跨区间的利润
    cross_profit = max_right_val - min_left_val
    cross_i, cross_j = min_left_idx, max_right_idx
    
    # 从三种情况中选出最优解
    max_profit = left_profit
    best_i, best_j = left_i, left_j
    
    if right_profit > max_profit:
        max_profit = right_profit
        best_i, best_j = right_i, right_j
    
    if cross_profit > max_profit:
        max_profit = cross_profit
        best_i, best_j = cross_i, cross_j
    
    return max_profit, best_i, best_j

# 测试示例
array = [10, 4, 5, 2, 2, 2, 3, 1, 7, 10]
profit, i, j = find_max_profit_divide_conquer(array, 0, len(array)-1)
print(f"最优解：i={i}（A[i]={array[i]}），j={j}（A[j]={array[j]}），利润={profit}")

时间复杂度验证 #

递归式为T(n) = 2T(n/2) + Θ(n)：

• 每次递归将问题拆分为两个规模为n/2的子问题，耗时2T(n/2)
• 合并阶段需要遍历左右子区间找极值，总共遍历n个元素，耗时Θ(n)

根据主定理的case2，总时间复杂度为Θ(nlogn)，完全符合需求。

内容的提问来源于stack exchange，提问作者gybonel