3
\$\begingroup\$

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))
\$\endgroup\$
2
  • \$\begingroup\$ Is this the only list you have to deal with, or will it be necessary to process something much longer? \$\endgroup\$
    – Reinderien
    Feb 15, 2022 at 23:17
  • \$\begingroup\$ That's the example we worked with, but it can be longer \$\endgroup\$
    – D.Zou
    Feb 15, 2022 at 23:22

3 Answers 3

6
\$\begingroup\$

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()

performance measurement

The linear methods can scale to the millions of elements:

performance measurement linear

\$\endgroup\$
2
  • \$\begingroup\$ This is interesting, but how does it ensure we buy first sell after? \$\endgroup\$
    – D.Zou
    Feb 16, 2022 at 0:07
  • \$\begingroup\$ @D.Zou It didn't; but it does now. \$\endgroup\$
    – Reinderien
    Feb 16, 2022 at 15:22
4
\$\begingroup\$

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
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Very good! I've included your implementation in my timings. Algorithmically it's very efficient, and the only way I've found to do better is to vectorise it. \$\endgroup\$
    – Reinderien
    Feb 16, 2022 at 14:39
0
\$\begingroup\$

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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.