Finding the path with max sum using DFS takes too long

Question

At each time point agent can:

• open one position if he has enough funds. This reduces funds by current price. The price is added to the list of open positions
• close one position (the one opened farthest in time) if he has open positions. This adds current price to funds, removes position from the list and increases profit by current price minus open price.
• hold (do nothing).

Given an array of prices, the aim is to find optimal open/close moments to get maximum profit.

I have implemented this, but the code runs very long (1 minute for 16 observations). What are the possibilities for the improvement?

Also, I want to get the optimal path itself. I can not store all the paths. What's the algorithm for backtracking?

Here is the code using Python:

import matplotlib.pyplot as plt
from collections import deque
import numpy as np
import time

def optimal_strategy(prices, root):
    s = deque([root])
    m = 0.0
    while s:
        n = s.pop()
        t = n['time'] + 1
        if t == len(prices):
            m = np.max([m, n['profit']])
            continue
        p = prices[t]
        s.append({'name': 'h' + str(t), 'time': t, 'parent': n['name'],
                  'funds': n['funds'], 'positions': n['positions'], 'profit': n['profit']})
        if p < n['funds']:
            s.append({'name': 'ol' + str(t), 'time': t, 'parent': n['name'],
                      'funds': n['funds'] - p, 'positions': n['positions'] + [p], 'profit': n['profit']})
        if len(n['positions']) > 0:
            s.append({'name': 'cl' + str(t), 'time': t, 'parent': n['name'],
                      'funds': n['funds'] + p, 'positions': n['positions'][1:], 'profit': n['profit'] + p - n['positions'][0]})

    return m

nobs = 16
np.random.seed(1)
prices = np.cumsum(np.random.normal(size=nobs))
plt.plot(prices)

t0 = time.time()
m = optimal_strategy(prices, {'name': 'r', 'time': -1, 'parent': None,
                              'funds': 4.0, 'positions': [], 'profit': 0.0})
print('Time {} Max {}'.format(time.time() - t0, m))

Answer 1

Here is an example showing how to get the exact trades that lead to the maximum funds. Maximizing funds guarantees that we maximized profits. Detailed calculations about which trades earned what profit can be calculated after we know the sequence.

from collections import namedtuple

Trade = namedtuple("Trade", "time funds shares parent")

def optimal_strategy (prices, funds):
    root = Trade(-1, funds, 0, None)
    portfolios = [root]
    for i, price in enumerate(prices):
        # Start with the option of holding.
        next_portfolios = portfolios.copy()
        for portfolio in portfolios:
            # Can we sell?
            next_funds = portfolio.funds + price
            next_shares = portfolio.shares - 1
            if 0 <= next_shares and 0 <= next_funds:
                if next_portfolios[next_shares].funds < next_funds:
                    next_portfolios[next_shares] = Trade(
                        i, next_funds, next_shares, portfolio)
            # Can we buy?
            next_funds = portfolio.funds - price
            next_shares = portfolio.shares + 1
            if 0 <= next_funds:
                if len(next_portfolios) == next_shares:
                    next_portfolios.append(Trade(
                        i, next_funds, next_shares, portfolio))
                elif next_portfolios[next_shares].funds < next_funds:
                    next_portfolios[next_shares] = Trade(
                        i, next_funds, next_shares, portfolio)
        portfolios = next_portfolios

        # Remove portfolios that cannot lead to our answer.
        while len(prices) - i < len(portfolios):
            portfolios.pop()

    path = []
    portfolio = portfolios[0]
    parent_portfolio = portfolio.parent
    while parent_portfolio is not None:
        if parent_portfolio.shares < portfolio.shares:
            path.append((portfolio.time, 'buy'))
        else:
            path.append((portfolio.time, 'sell'))
        portfolio = parent_portfolio
        parent_portfolio = portfolio.parent
    return list(reversed(path))