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)
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:
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.