分而治之最大利润算法

Question

我需要找到一个具有复杂性的分而治之算法（针对最大利润问题）

Θ(nlogn)

，但我只能找到具有复杂性的

Θ(n)

。

最大利润问题是基于股票的。例如：

array = [10, 4, 5, 2, 2, 2, 3, 1, 7, 10]

在这里，您需要在给定数组中找到

max(A[j] - A[i])

，但您需要有

j > i

（因为您无法回到过去并购买股票，假设它被创建的那一天）。所以在这个数组中，解决方案是

j = 8

（数组中的第 8 个元素），带有

A[j] = 10

和

i = 6

。

我当前的代码是

def find_max_profit_2(A, low, high):

    if low > high:
        return None

    if low == high:
        return low, low

    middle = (low + high) // 2

    j_a, i_a = find_max_profit_2(A, low, middle)
    j_b, i_b = find_max_profit_2(A, middle + 1, high)

    ret_j, ret_i = 0 , 0

    if A[j_a] > A[j_b]:
        ret_j = j_a
    else:
        ret_j = j_b

    if  A[i_a] < A[i_b]:
        ret_i = i_a
    else:
        ret_i = i_b

    return ret_j, ret_i

with

T(n) = 2T(n/2) + Θ(1)

--> 根据主定理案例 1，我的代码的时间复杂度是

T(n) = Θ(n).

请记住，目标是找到 T(n) = θ(nlogn) 的代码

Answer 1

似乎要使用分而治之的方法实现最大利润问题的时间复杂度

Θ(n log n)

，我们需要修改算法，以便每个除法步骤比简单的

Θ(1)

比较对整体复杂性的贡献更大。

步骤是：

1. 将数组分成两半（就像您已经在做的那样）。
2. 递归地找到每一半的最大利润。这与您当前的方法类似。
3. 找到穿过中点的最大利润。这一步至关重要。它涉及找到买点在左半部分、卖点在右半部分的最大利润。此步骤每划分的复杂度应为 θ(n)。

def find_max_profit_crossing(A, low, mid, high):
    # Finding the minimum price in the left half
    min_price = min(A[low:mid+1])
    # Finding the maximum profit in the right half
    max_profit = max([A[j] - min_price for j in range(mid+1, high+1)])
    return max_profit

def find_max_profit(A, low, high):
    if low == high:
        return 0

    mid = (low + high) // 2

    # Maximum profit in left half
    left_profit = find_max_profit(A, low, mid)

    # Maximum profit in right half
    right_profit = find_max_profit(A, mid + 1, high)

    # Maximum profit crossing the midpoint
    cross_profit = find_max_profit_crossing(A, low, mid, high)

    return max(left_profit, right_profit, cross_profit)

因此，在该算法中，每次递归调用都会将问题一分为二（

Θ(log n)

拆分），并且对于每次拆分，

find_max_profit_crossing

函数都会计算线性时间内穿过中点的最大利润 (

Θ(n)

)。因此，根据分治递归的主定理，整体复杂度变为

Θ(n log n)

。