1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ You did not missing anything. Your implementation is better. Your analysis is correct. I recommend that you edit the question so that it is titled "Can the maximum single sell profit by divide and conquer be O(n) ?", explaining the O(n log n) algorithms known to you. Then write an answer with your algorithm. $\endgroup$
    – John L.
    Commented Mar 7, 2021 at 9:28

1 Answer 1

1
$\begingroup$

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
$\endgroup$
3
  • 2
    $\begingroup$ Although as you wrote it, your code does actually run in $\Theta(n\log n)$ time as you are doing a linear amount of work when creating the subproblems (when slicing, i.e. prices[: len(prices) // 2]). This can be corrected by never copying the list and calling the helper function with two integers representing the start and end index of the currently considered subproblem. $\endgroup$
    – Tassle
    Commented Mar 7, 2021 at 23:43
  • $\begingroup$ I did not know a Python slice operation was O(k). Thanks for that. Fixed. $\endgroup$
    – mike
    Commented Mar 8, 2021 at 4:14
  • $\begingroup$ A very nice answer! $\endgroup$
    – John L.
    Commented Mar 8, 2021 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.