Implementation of single-sell profit problem

We start by defining a small list of prices, and then defining the brute-force solution, which returns a tuple of (buy_index, sell_index, profit). We see that the best solution is to buy on day 4 for 1 dollar, then sell on day 5 for 9 dollars.

all_prices = [10, 5, 8, 12, 1, 9, 3, 7]

def brute_force(prices):
    best = (0, 1, prices[1]-prices[0])
    for i in range(len(prices)-1):
        for j in range(i+1, len(prices)):
            if prices[j]-prices[i] > best[2]:
                best = (i, j, prices[j]-prices[i])
    return best

print(all_prices)
brute_force(all_prices)

[10, 5, 8, 12, 1, 9, 3, 7]

(4, 5, 8)

Now we define the divide-and-conquer solution. Here’s a textual description of the code.

Base Cases

• For lists of length 2, we have no choice buy to buy on the first day and sell on the second.

• For lists of length 3, we have three choices - we return the one with the largest profit.

Divide

• We split the list into two lists, left and right, and call the function recursively on each half

• left_best now contains the best buy-sell indices if we were limited to just the left half. Same with right_best

Combine

• In our larger array, the best choice is one of:

  1. The solution from the left half

  2. The solution from the right half (with indices adjusted to be correct - the index i in right is index i+len(left) in the full array prices)

  3. The solution that is buying from the cheapest day in left and the most expensive day in right

• We return the solution that is best of those three.

We run it on our list, and see we get the same answer.

def max_profit(prices):
    if len(prices)==2:
        return (0, 1, prices[1]-prices[0])
    if len(prices)==3:
        choices = [ (0, 1, prices[1]-prices[0]), # buy on day 0, sell on day 1
                    (0, 2, prices[2]-prices[0]), # buy on day 0, sell on day 2
                    (1, 2, prices[2]-prices[1]) ]# buy on day 1, sell on day 2
        return max(choices, key=lambda x:x[2])

    mid = len(prices)//2
    left = prices[:mid]
    right = prices[mid:]

    left_best = max_profit(left)
    right_best = max_profit(right)

    right_max = max(right)
    right_max_index = right.index(right_max)+len(left)

    left_min = min(left)
    left_min_index = left.index(left_min)

    choices = [left_best, (right_best[0]+len(left), right_best[1]+len(left), right_best[2]), (left_min_index, right_max_index, right_max-left_min)]
    return max(choices, key=lambda x:x[2])

print(all_prices)
max_profit(all_prices)

[10, 5, 8, 12, 1, 9, 3, 7]

(4, 5, 8)

We know the brute-force is \(O(n^2)\) and the D&C is \(O(n\log(n))\). What does this mean practically? We see that even with this small list, the max_profit is noticeably faster than brute_force.

import time

start = time.time()
print(brute_force(all_prices))
end = time.time()
print(f'  {end-start}')

start = time.time()
print(max_profit(all_prices))
end = time.time()
print(f'  {end-start}')

(4, 5, 8)
  7.772445678710938e-05
(4, 5, 8)
  5.078315734863281e-05

We now make a much bigger list, of size 20000. The difference in speed is even more pronounced (as we would expect). D&C is much faster.

import random
all_prices = [random.randint(1,10000) for _ in range(20000)]

import time

start = time.time()
print(brute_force(all_prices))
end = time.time()
print(f'  {end-start}')

start = time.time()
print(max_profit(all_prices))
end = time.time()
print(f'  {end-start}')

(2592, 8722, 9999)
  5.707004547119141
(2592, 8722, 9999)
  0.008918046951293945

Greedy solution

There’s actually a greedy solution to this problem, too, which is even faster (\(O(n)\)). The core idea is, what if I sold today? By tracking the minimum price seen so far, and the best profit achieved so far, we can iterate once through the list, and come up with an optimal solution even faster.

def greedy_profit(prices):
    min_buy_price = prices[0]
    min_buy_index = 0
    max_profit = 0
    
    buy_index = 0
    sell_index = 0

    for i in range(1, len(prices)):
        current_price = prices[i]
        
        potential_profit = current_price - min_buy_price
        
        if potential_profit > max_profit:
            max_profit = potential_profit
            buy_index = min_buy_index
            sell_index = i

        if current_price < min_buy_price:
            min_buy_price = current_price
            min_buy_index = i
            
    return buy_index, sell_index, max_profit

import time

start = time.time()
print(brute_force(all_prices))
end = time.time()
print(f'  {end-start}')

start = time.time()
print(max_profit(all_prices))
end = time.time()
print(f'  {end-start}')

start = time.time()
print(greedy_profit(all_prices))
end = time.time()
print(f'  {end-start}')

(2592, 8722, 9999)
  5.695568323135376
(2592, 8722, 9999)
  0.008890628814697266
(2592, 8722, 9999)
  0.0005767345428466797