Divide and Conquer max profit algorithm

Question

I need to find a Divide and Conquer algorithm (for the max profit problem) with complexity Θ(nlogn) but I am only able to find with complexity Θ(n).

The max profit problem is based on stocks. For example:

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

Here you need to find the max(A[j] - A[i]) in the given array, but you need to have j > i (as you cannot go back to time and buy the stock lets say the day it was created).So in this array the solution is j = 8 (the 8th element in the array) with A[j] = 10 and i = 6.

My current code is

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) --> From Master Theorem case 1 the time complexity of my code is T(n) = Θ(n).

Remember the objective is to find a code with T(n) = Θ(nlogn)

Answer 1

It seems that to achieve a time complexity of Θ(n log n) for the maximum profit problem using a divide and conquer approach we need to modify the algorithm so that each division step contributes more to the overall complexity than a simple Θ(1) comparison.

Steps are:

1. Divide the array into two halves (as you are already doing).
2. Recursively find the maximum profit in each half. This is similar to your current approach.
3. Find the maximum profit that crosses the midpoint. This step is crucial. It involves finding the maximum profit where the buying point is in the left half and the selling point is in the right half. This step should have a complexity of Θ(n) per division.

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)

So in this algorithm, each recursive call splits the problem in half (Θ(log n) splits), and for each split, the find_max_profit_crossing function computes the maximum profit that crosses the midpoint in linear time (Θ(n)). Thus, the overall complexity becomes Θ(n log n), as per the Master Theorem for divide-and-conquer recurrences.