Buy and sell stock twice

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

There are a lot of moving parts to keep track of. Let's use a data type to keep things orderly.

import collections
TXN = collections.namedtuple('TXN', ('buy_date', 'sell_date', 'profit'))

First get the optimum buy/sell dates if we are only buying and selling just once.

def brute_force(prices: list[int]) -> Optional[TXN]:
    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 = TXN(buy_date, sell_date, profit)

    if max_profit_so_far:
        return transaction_dates

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

Now split up the given list into 2 sublists, where each sublist must have length 2 or greater. The length must be at least 2, because this is the minimum length for buying and selling. Now run brute_force against each of these sublists. If the two buy/sell transactions' combined profit is greater than the single transaction's profit, we take note of it.

def brute_force_sublists(prices: list[int]
    ) -> Optional[tuple[TXN, TXN]]:

    # There are 2 sublists and each one must have at least 2 items.
    if len(prices) < 4:
        return None

    # Divide up prices into sublists.
    sublists = [(prices[0:i], prices[i:])
    for i in range(0, len(prices))
    if i > 1 and len(prices) - i > 1]

    txn_dates = None
    max_sell_twice = 0
    for list1, list2 in sublists:
        txn1 = brute_force(list1)
        txn2 = brute_force(list2)
        if txn1 is not None and txn2 is not None:
            if txn1.profit + txn2.profit > max_sell_twice:
                # The indices (dates) for txn2 are wrong because list2 will
                # start at its own index 0. So we need to give the dates an
                # offset.
                txn2 = txn2._replace(buy_date = txn2.buy_date + len(list1))
                txn2 = txn2._replace(sell_date = txn2.sell_date + len(list1))

                txn_dates = (txn1, txn2)
                max_sell_twice = max(txn1.profit + txn2.profit,
                                    max_sell_twice)

    if max_sell_twice:
        return txn_dates

    return None

Now that we know how to calculate the max profit for a single transaction as well as two transactions, we just have to compare them and see which one has a greater profit.

def brute_force_maybe_sell_twice(prices: list[int]
    ) -> Optional[tuple[Optional[TXN], Optional[TXN]]]:

    txn = brute_force(prices)
    txn_pair = brute_force_sublists(prices)

    # If there's no way to make a profit with a single sale, give up.
    if txn is None:
        return None

    if txn_pair is None:
        return txn, None

    max_sell_twice = txn_pair[0].profit + txn_pair[1].profit

    if max_sell_twice > txn.profit:
        return txn_pair

    # If the max_sell_twice profit wasn't bigger, then the best we got is the
    # one from the one sale in txn.
    return txn, None

The first pass is basically the same as optimal() from "Buy and sell stock once", but applied twice – once "forward" and again "backward". In the first pass, we record the max possible profit if we're selling on that day. This pass is basically the same as the optimum solution in "Buy and sell stock once". The algorithm there iterates through each price, keeps a running minimum price seen (this assumes buying at that time), and records a profit or loss by selling on the day it is looking at.

Then we can do a second pass by iterating through each day in reverse, getting the max profit if we we're buying on that day — this is the inverse of the first pass because we track the running maximum price (thereby assuming that we sell on that day). The current day we're looking at is the day of the second purchase. During this second pass we can use the information from the first pass to determine the max possible profit for buying and selling twice.

Essentially these two passes, on their own, can get the same answer for the scenario of buying and selling once. The first one asks "assuming that we bought already and must sell today, how much money can I make?" while the second one asks "assuming that we must sell sometime in the future and must buy today, how much money will I make?". They are two sides of the same coin. The key property of the second question though, is that we can ask it while iterating backwards in time, such that we only have to iterate backwards once, just like how we can iterate forwards once with the first algorithm. Using these two complementary styles minimizes the number of traversals because we can burn the candle at both ends, so to speak.

def two_pass_maybe_sell_twice(prices: list[int]
    ) -> Optional[tuple[Optional[TXN], Optional[TXN]]]:
    if len(prices) < 2:
        return None

    min_price_so_far = float('inf')
    max_profit_sell_once = 0
    txn1 = None
    txn2 = None
    profit_txn1 = [TXN(-1, -1, -1)] * len(prices)

    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

        if max_profit_if_sell_now > max_profit_sell_once:
            max_profit_sell_once = max(int(max_profit_if_sell_now),
                                        max_profit_sell_once)
            txn1 = TXN(buy_date, date, max_profit_sell_once)

        if txn1 is not None:
            profit_txn1[date] = txn1

    # Our current understanding of the max possible profit is by looking at one
    # buy and one sell.
    max_profit = max_profit_sell_once

    # Now consider a second sale.
    max_price_so_far = 0
    for date, price in reversed(list(enumerate(prices[2:], 2))):
        if price >= max_price_so_far:
            sell_date = date
            max_price_so_far = max(max_price_so_far, price)

        profit_txn2 = max_price_so_far - price

        if profit_txn2 <= 0:
            continue

        max_profit_sell_twice = profit_txn1[date - 1].profit + profit_txn2
        if max_profit_sell_twice < max_profit:
            continue

        # If selling once or twice gives us the same profit, then just sell
        # once.
        if txn1 is not None and txn1.profit == max_profit_sell_twice:
            continue

        max_profit = max(max_profit, max_profit_sell_twice)
        txn1 = profit_txn1[date - 1]
        txn2 = TXN(date, sell_date, profit_txn2)

    if txn1 is None:
        return None

    return txn1, txn2

In the second pass, we do price >= max_price_so_far instead of the simpler price > max_price_so_far because we want to agree exactly with the brute force approach. For example, consider the case

1  2  1  1  2  (prices)
0  1  2  3  4  (day number)

Obviously there must be two transactions in order to maximize profit here, buying at price 1 and selling at price 2 (we do this twice). However for the second transaction we could buy at price 1 on day 2 or day 3 — the profit at the end is the same. The brute force approach splits into sublists and looks at prices going left to right in both sublists, but for the two-pass algorithm, for the second pass, the prices are looked at right to left. In order to make the two-pass algorithm override its previous choice of day 3 with day 2, we use the >= sign.

This algorithm only requirse a single pass, and also only uses \(O(1)\) space complexity, improving on the two-pass algorithm (eefiasfira (https://cs.stackexchange.com/users/107747/eefiasfira), n.d.). It is able to do this by keeping track of three maximum values. It is slightly different than the style of solutions we've looked at so far because it does not keep track of the buy and sell dates.

The key is to assume that a second buy has occurred at some previous iteration, and then to see how much profit we can make after a second sale if we assume that we can sell for a second time today (in the current iteration).

def single_pass_maybe_sell_twice(prices: list[int]
    ) -> Optional[int]:
    if len(prices) < 2:
        return None

    min_price_so_far = float('inf')
    max_profit_after_first_sell = 0
    max_profit_after_second_buy = float('-inf')
    max_profit_after_second_sell = 0

    for price in prices:
        min_price_so_far = min(price, min_price_so_far)
        max_profit_after_first_sell = max(
            int(price - min_price_so_far),
            max_profit_after_first_sell)
        max_profit_after_second_buy = max(
            max_profit_after_first_sell - price,
            max_profit_after_second_buy)
        max_profit_after_second_sell = max(
            int(price + max_profit_after_second_buy),
            max_profit_after_second_sell)

    if max_profit_after_second_sell:
        return max_profit_after_second_sell

    return None

Variables min_price_so_far and max_profit_after_first_sell are the essentially the same variables used in the optimum solution for "Buy and sell stock once".

Variable max_profit_after_second_buy will only track the cheapest price available while still assuming the context of max_profit_after_first_sell. It's like tracking a second minimum price value (for the best value for the second buy), except that we track the maximum (leftover) profit to be made. The corresponding max_profit_after_second_sell variable just checks what the total profit would be assuming a second sale; the neat thing is that it already has the profits from the first sale accounted for.

One difference with this algorithm than the other approaches we've seen so far is that it considers selling stock on the same day that it bought stock.

You may also be wondering if it is possible to tweak this algorithm to keep track of the buy and sell dates (as we have done in the other algorithms). This is not possible. For example, consider the following input: [3, 4, 2, 5, 1, 6]. When we see the price at 1, we will set this as the new min_price_so_far. However by setting this value, we make this the date of the first buy date (as it is used for calculating max_profit_after_first_sell), which is wrong (it should be the second buy date).