pythonoptimizationtime-complexitycomplexity-theorydivide-and-conquer

# Divide and Conquer max profit algorithm

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)

Solution

• 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.