Answering my own question, yes! The trick is to do the work to compute the max and min of the sublists in the divide-and-conquer recursion rather than when merging the results.
To do this, you need an inner function that returns not just the best trade in a subproblem, but also it's min and max. The combine step is then $O(1)$ rather than $O(n)$.
Here's what that looks like:
def best_trade(prices: List[int]) -> int: """ Divide-and-conquer in O(n). """ def f(start: int, end: int) -> Tuple[int, int, int]: if start == end: return 0, prices[start], prices[start] else: best_left, min_left, max_left = f( start, start + (end - start) // 2, ) best_right, min_right, max_right = f( start + (end - start) // 2 + 1, end, ) return ( max(best_left, best_right, max_right - min_left), min(min_left, min_right), max(max_left, max_right), ) # `else 0` for the corner case where prices = [] return f(0, len(prices) - 1)[0] if prices else 0 Note that the inner function passes the start and end index of the subproblem down the stack, rather than taking slices, because taking slices is $O(k)$, where $k$ is the length of the slice. By passing pointers we keep the work done outside the recursion to $O(1)$.
With this implementation, $T(n) = 2 T(n/2) + O(1)$ which implies this divide-and-conquer algorithm is $O(n)$.
The general pattern here is to do more work (or return more information) than is strictly necessary in the recursion to reduce the work outside the recursion. In this case, the "extra" work done inside the recursion is trivial, so the running time is significantly reduced, at the cost of a slightly less legible bit of code.
One final point: of course the single scan solution is also $O(n)$ and significantly simpler than either divide-and-conquer solution:
def best_trade(prices: List[int]) -> int: """ Single scan in O(n). """ if not prices: return 0 lowest = prices[0] best = 0 for p in prices: lowest = min(p, lowest) best = max(best, p - lowest) return best