README.org

Buy and sell stock once

Problem statement

Given a list of prices for a stock over the past N days (one price per day), determine the optimum days to buy and sell the stock once to maximize profit [cite:@epip 51].

Inputs and outputs

• Input: list of stock prices (positive numbers)
• Output: day to buy the stock, day to sell the stock, and the realized profit margin

Insights

Simply taking the minimum and maximum values of the entire range, and comparing these two numbers, won’t work. Example: [10, 5]. Here the only possible buy and sale is to buy at price 10 and sell on the next day at price 5. But doing so would result in a loss. If the price is decreasing each day, then every possible buy/sell combination will result in a loss. In this situation the algorithm should not recommend a buy/sell transaction at all (do nothing).

Here’s another example: [10, 9, 8, 1, 2, 6]. Here the maximum possible profit is to buy at 1 and sell at 6, for a profit margin of 5. The minimum and maximum prices are 1 and 10, which are interesting but don’t give us the answer.

Solutions

Brute force

Compare every number in the list with every other number. That is, compute every possible combinationa of buy/sell dates, and just return the best (max profit) dates found.

def brute_force(prices: list[int]) -> Optional[tuple[int, int, int]]:
    if not prices:
        return None

    max_profit_so_far = 0
    for buy_date, price_buy in enumerate(prices):
        for sell_date in range(buy_date + 1, len(prices)):
            profit = prices[sell_date] - price_buy
            if profit > max_profit_so_far:
                max_profit_so_far = profit
                transaction_dates = (buy_date, sell_date, profit)

    if max_profit_so_far:
        return transaction_dates

    # If no profitable trade found, return None.
    return None

The time complexity is $O(n^2)$ where $n$ is the length of the list of prices.

Optimal

For the optimal solution, the key is to pretend to sell on that day, using the minimum price found in the previous days as the buying point. The trick here is that the previous minimum price calculation can be updated on each iteration with just a single min() comparison.

def optimal(prices: list[int]) -> Optional[tuple[int, int, int]]:
    if not prices:
        return None

    min_price_so_far = float('inf')
    max_profit = 0

    for date, price in enumerate(prices):
        if price < min_price_so_far:
            buy_date = date
            min_price_so_far = min(price, min_price_so_far)

        max_profit_if_sell_now = price - min_price_so_far
        max_profit_prev = max_profit
        max_profit = max(int(max_profit_if_sell_now), max_profit)

        if max_profit > max_profit_prev:
            transaction_dates = (buy_date, date, max_profit)

    if max_profit:
        return transaction_dates

    # If no profitable trade found, return None.
    return None

The time complexity is $O(n)$.

As maximum subarray

As [cite/t:@cormen 69] point out, if we look at stock prices not as the prices themselves but as changes in price on each day, then the problem of finding the best buy/sell dates is the same as finding the maximum subarray.

The only annoying thing though, is that the indices are off by 1 (either the buy or sell date) because we lose 1 element to construct the changes array (the transformation of data from the list of prices to the list of changes is lossy). Still, the maximum achievable profit is accurate, and agrees with our optimal solution.

def via_max_subarray(prices: list[int]) -> Optional[tuple[int, int, int]]:
    if not prices:
        return None

    changes = [b - a for (a, b) in zip(prices, prices[1:])]
    max_subarray = dp(changes)
    if max_subarray is None:
        return None

    return (max_subarray.end, max_subarray.end, max_subarray.sum)

Tests

from hypothesis import given, strategies as st
import unittest

from typing import Optional

from maximum_subarray.maximum_subarray import dp

__NREF__brute_force

__NREF__optimal

__NREF__via_max_subarray

class Test(unittest.TestCase):
    cases = [
        ([],                      None),
        ([0],                     None),
        ([0, 0, 0, 0],            None),
        ([3, 2, 1],               None),
        ([5, 25, 100, 50],        (0, 2, 95)),
        ([5, 25, 100, 1, 50, 99], (3, 5, 98)),
    ]

    def test_simple_cases(self):
        for given_prices, expected in self.cases:
            self.assertEqual(brute_force(given_prices), expected)
            self.assertEqual(optimal(given_prices), expected)

            # Check via_max_subarray() (partial) solution. We can't check the
            # exact buy/sell dates because of off-by-1 errors.
            result = via_max_subarray(given_prices)
            if expected is not None and result is not None:
                self.assertEqual(result[2], expected[2])
            else:
                self.assertEqual(result, expected)

    @given(st.lists(st.integers(min_value=1, max_value=100), min_size=0,
                    max_size=14))
    def test_random(self, given_prices: list[int]):
        got = brute_force(given_prices)

        # If the prices were not always decreasing, then there must have been
        # some optimum buy/sell date.
        if given_prices and max(given_prices) > given_prices[0]:
            self.assertNotEqual(got, None)

        # Check that the optimal solution agrees with brute force.
        self.assertEqual(optimal(given_prices), got)

        # Check via_max_subarray() (partial) solution, like we did for
        # test_simple_cases().
        result = via_max_subarray(given_prices)
        if got is not None and result is not None:
            self.assertEqual(result[2], got[2])
        else:
            self.assertEqual(result, got)

if __name__ == "__main__":
    unittest.main(exit=False)

References