A better way to calculate Profit-n-Loss

Question

So the problem is as follows: given a list of prices, what is the max possible PnL? so to buy low sell high what is the max profit possible?

right now my solution involves making a copy of the list, traverse the both lists and compare the diff in the price movements.

things to consider: you have to buy first then sell: so the high price must come after the low price.

daily_price_list = [1, 8, 1, 2, 5, 7,-2,10,-5] 
daily_price_listB = daily_price_list
pnl = []

for price in (daily_price_list):
    price_move = []
    for index, _ in enumerate(daily_price_listB):
        price_move.append(daily_price_listB[index] - price)
    daily_price_listB = daily_price_listB[1:]

    pnl.append(max(price_move))
print(max(pnl))

Answer 1

Now that I understand the problem (sorry for being hasty!):

The first algorithmic approach is an O(n²) solution, but

1. this can be done in a vectorised manner with Numpy and will execute more quickly than the original solution that uses manual loops; and
2. very importantly, as @setris has demonstrated, this can be done in linear time instead.

The basic idea for an O(n²) solution is: compute a broadcasted matrix of differences between every element pair; lower-triangularise to enforce that you can only sell after buying; and then find the maximum of the whole matrix. Of course this is not the only vectorised method.

The fastest method uses a vectorised cumulative minimum and is linear in both space and time.

from timeit import timeit

import numpy as np
import pandas as pd
import seaborn as sns
from matplotlib import pyplot as plt
from numpy.random import default_rng


def op_method(daily_price_list):
    daily_price_listB = daily_price_list
    pnl = []

    for price in (daily_price_list):
        price_move = []
        for index, _ in enumerate(daily_price_listB):
            price_move.append(daily_price_listB[index] - price)
        daily_price_listB = daily_price_listB[1:]

        pnl.append(max(price_move))
    return max(pnl)


def broadcast(prices):
    return np.tril(
        prices[:, np.newaxis] - prices[np.newaxis, :]
    ).max()


def by_index(prices):
    profits = prices[:, np.newaxis] - prices[np.newaxis, :]
    return profits[np.tril_indices(len(prices))].max()


def from_flat(prices):
    i, j = np.tril_indices(len(prices))
    return (prices[i] - prices[j]).max()


def setris(stock_prices):
    lowest_price_seen_so_far = float("inf")
    maximum_profit = 0

    for price in stock_prices:
        profit = price - lowest_price_seen_so_far
        maximum_profit = max(maximum_profit, profit)
        lowest_price_seen_so_far = min(lowest_price_seen_so_far, price)

    return maximum_profit


def cumulative(prices):
    minima = np.minimum.accumulate(prices)
    return (prices - minima).max()


METHODS = (op_method, broadcast, by_index, from_flat, setris, cumulative)


def test():
    for method in METHODS:
        assert 12 == method(np.array((1, 8, 1, 2, 5, 7, -2, 10, -5)))
        assert 30 == method(np.array((310, 315, 275, 295, 260, 270, 290, 230, 255, 250)))


def measure():
    rand = default_rng(0)
    times = []

    for n_log in 10**np.linspace(0.5, 3, 250):
        n = round(n_log)
        prices = rand.random(n)
        for method in METHODS:
            def run():
                return method(prices)
            t = timeit(run, number=1)
            times.append((
                method.__name__, n, t,
            ))

    df = pd.DataFrame(times, columns=('method', 'n', 't'))
    ax = sns.lineplot(data=df, x='n', y='t', hue='method')
    ax.set(xscale='log', yscale='log')
    plt.show()


if __name__ == '__main__':
    test()
    measure()

The linear methods can scale to the millions of elements:

Answer 2

The maximum profit we can make by selling a stock at time \$t\$ (e.g. given a sequence of stock prices [310, 315, 275, 295], \$price_0=310\$ is the price at \$t=0\$, \$price_1=315\$ is the price at \$t=1\$, etc.) can be found by

$$ price_t - min(price_0..price_{t-1}) $$

or in other words, subtracting the lowest previously-seen stock price from the current stock price. We can do this for all the prices in the sequence and determine the overall maximum profit in one pass.

The following solution runs in \$O(n)\$ time and \$O(1)\$ space.

def max_profit(stock_prices):
    lowest_price_seen_so_far = float("inf")
    maximum_profit = 0

    for price in stock_prices:
        profit = price - lowest_price_seen_so_far
        maximum_profit = max(maximum_profit, profit)
        lowest_price_seen_so_far = min(lowest_price_seen_so_far, price)

    return maximum_profit

Answer 3

If we create two arrays lowest_price_before and highest_price_after, we can calculate the maximum pnl by taking the max of highest_price_after[t] - lowest_price_before[t] where t loops over the indices. This all can be done in linear time.

If we now inline the computation of the maximum of this expression, we only need a single array:

daily_price_list = [1, 8, 1, 2, 5, 7,-2,10,-5] 

highest_price_after = []
highest_price = daily_price_list[-1]
for price in reversed(daily_price_list):
    highest_price = max(highest_price, price)
    highest_price_after.insert(0, highest_price)

best_pnl = 0
lowest_price = daily_price_list[0]
for (t, price) in enumerate(daily_price_list):
    lowest_price = min(lowest_price, price)
    best_pnl = max(best_pnl, highest_price_after[t] - lowest_price)

print(best_pnl)

(For good performance, the next step would probably be to allocate highest_price_after in a single step)