Can the maximum single sell profit by divide and conquer be O(n)?

Question

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)$?

Answer 1

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