Buy and Sell Two Stocks

Problem

Given an array of integers representing stock prices, with each index representing a different day, find the maximum profit by selling at most two stocks. The buy/sell dates must not overlap.

Input

• A: An array of \(n\) integers
  • \(n\geq0\)

Approach

The approach to buying and selling one stock is to keep track of the minimum number. A buy and sell sequence starts when you encounter a number smaller than the current minimum. As you move along in the sequence, the goal is to encounter a larger number than the current minimum. Taking the difference of the larger number with the current minimum gives you the profit for that buy/sell sequence. All that must be done now is to only record the highest profit for each buy/sell sequence you run into, and return that profit number. Note that this is a very textbook greedy algorithm, because we do not backtrack from the results we have recorded, and we are always finding the local optimum at each index.

When two stocks are involved, things can get drastically tricky. With the formula above, you may be able to greedily find the highest profit obtainable in one sequence, but the second stock option might not be so rewarding. In fact, sometimes you will actually find that an even higher profit can be obtained by combining two lesser profits.

Suppose that you have an array \(X = {310, 315, 260, 270, 290, 280, 315}\), where the number represents the price. If we try to apply the greedy algorithm here, we will first buy at \(260\) and sell at \(315\) to make \(55\) as profit. This leaves \(310\) and \(315\) as the only other stock to buy/sell, which nets us \(5\) as profit, for a total of \(60\) profit.

At first glance, \(60\) might seem very good, but this isn't the best solution. In fact, the best solution is to buy at \(260\), sell at \(290\), and then buy \(280\) and sell at \(315)\), which gives us a total of \(65\) as profit. As you can see, the greedy algorithm approach shows its flaws here.

The running profit

The key to optimizing the solution for this problem is to use a running tally of the profit. By keeping track of the maximum profit seen so far at each index, we can retrieve the maximum profit with ease.

In order to demonstrate this, here is a solution using the running profit trick for buying and selling one stock

def buy_and_sell_one_stock(A):  
    profit = 0
    min_so_far = A[0]
    running_profits = [0]
    for num in A[1:]:
        if num < min_so_far:
            min_so_far = num
        running_profits.append(max(running_profits[-1], num - min_so_far))
    return max(running_profits)

Two stocks with the running profit

We can leverage the fact that the buying and selling of two stocks cannot occur within the same days -- they cannot overlap.

By calculating the running profit in two separate iterations -- forward and backwards, we are able to find the maximum profit from buying and selling two stocks.

Coming back to the array \(X = {310, 315, 260, 270, 290, 280, 315}\), where the number represents the price, lets find the running profit in both iterative styles.

• Forward iteration: \({0, 5, 5, 10, 30, 30, 55}\)
• Backwards iteration: \({55, 55, 55, 45, 35, 35, 0}\)*

*In the backwards iteration, we start at the last element, set it as the max_so_far and iterate the array to the left. For each element (to the left) that is smaller than the current max_so_far, we calculate the profit and add it to the list -- more precisely at the index of the element we just looked at.

All that needs to be done now, is to add the \(i\)th element in the forward iteration to the \(i+1\)th element in the backward iteration. This is due to the fact that the buying and selling of stocks have to be done on non-overlapping days. After adding, your running profits should now look like this:

• Running totals: \({55, 60, 60, 55, 65, 65, 55}\)

Returning the maximum of the list above will get you the highest profit from buying and selling two stocks.

Solution

def buy_and_sell_stock_twice(A):  
    profit = 0
    min_so_far = A[0]

    running_profit_fwd = []
    running_profit_bwd = []

    for num in A:
        if num < min_so_far:
            min_so_far = num
        profit = max(profit, num - min_so_far)
        running_profit_fwd.append(profit)

    profit = 0
    max_so_far = A[-1]

    for num in reversed(A):
        if num >= max_so_far:
            max_so_far = num
        profit = max(profit, max_so_far - num)
        running_profit_bwd.append(profit)

    running_profit_bwd = running_profit_bwd[::-1]

    total_profits = [running_profit_bwd[0]]
    for i in range(1, len(running_profit_bwd)):
        total_profits.append(running_profit_bwd[i] + running_profit_fwd[i-1])

    return max(total_profits)