The single sell profit problem is:
Given a list of prices on each day, find the maximum profit that could have been made by buying on one of the days and selling on a later day.
There is a solution with a single scan that is easy to implement and runs in $O(n)$. This question is not about that. It's about the divide-and-conquer solution.
I've read twice that the divide-and-conquer solution to this problem is $O(n \log n)$: once when this problem is discussed in Elements of Programming Interviews in Python by Aziz, Lee and Prakash (it's problem 5.6), and once in these PDF lecture notes by Kevin Zatloukal of UW (page 23). Both these sources say the divide and conquer solution is slower than a simple scan.
Neither source presents an implementation (it's not the best approach, so fair enough), and the descriptions are a little terse, but reading between the lines they seem to describe a simple divide-and-conquer down to a base case of a single element, whether the merged result is the maximum of the best trade in the two subproblems and the maximum price in the right minus the maximum price in the left.
Here's that in Python
def best_trade(prices: List[int]) -> int:
if len(prices) < 2:
return 0
else:
best_left = best_trade_2(prices[: len(prices) // 2])
best_right = best_trade_2(prices[len(prices) // 2 :])
return max(
best_left,
best_right,
max(prices[len(prices) // 2 :]) - min(prices[: len(prices) // 2]),
)
The running time of this for a problem of size $n$, $T(n) = 2 T(n/2) + O(n)$ because the max
/min
call outside the recursion are O(n). By the Master Method analysis this means the algorithm has time complexity $O(n \log n)$ ($a = 2$, $b = 2$, $d = 1$ so we're in the $a = b^d$ case where the complexity is $O(n^d \log n)$).
My question is: can this problem be solved by divide-and-conquer in $O(n)$?