Maximum profit from buy and sell offers
1. Review


The code in the post does not always compute the highest profit. For example, suppose that I have these orders:

sell = [Order(price=1, amount=1, min_amount=np.nan)]
buy = [Order(price=1, amount=1, min_amount=1),
       Order(price=2, amount=1, min_amount=1)]
max_n = 2


Then the code computes:

buyprices = [0, 1]
profits = [0, 0]


In other words, the code sells to the first buyer, ignoring the second buyer who is prepared to pay more.
You clarified in comments that it's a requirement that the buyers be sorted by price. It would be more reliable if the code did any necessary sorting:

buy = buy[np.argsort(buy[:,0])]


Then you wouldn't have to worry about the order of the input.
Even if the input is sorted by price, the algorithm in the post still does not always compute the highest profit. For example, suppose that I have the following orders:

sell = [Order(price=1, amount=4, min_amount=np.nan)]
buy = [Order(price=6, amount=3, min_amount=3),
       Order(price=5, amount=2, min_amount=2),
       Order(price=5, amount=2, min_amount=2)]
max_n = 5


In this case, the code computes:

buyprices = [0, 0, 10, 18, 18]
profits = [0, -1, 8, 15, 14]


The highest profit it can find is 15, by selling three units to the first buyer. But if I sell two units to each of the second and third buyers, then I get a profit of 16.
Even with the orders given in the post, the code computes the wrong prices for some amounts. For example, you can see from the graph that the code thinks that it can sell 40 units for a price of 200. But there is no way to sell 40 units — you can sell 20 units to the third buyer, but no more than that, and the second buyer has a minimum order of 50.

Similarly, the code determines that it can sell 140 units for a price of 3200. But there is no way to make such a sale: if you sell 100 to the first buyer, then that leaves 40, and there is no way to sell 40 units (as discussed above). So you have to sell to the second buyer, in which case the best price you can get is 2100.

I believe that the correct graph looks like this, with a gap between 20 and 50, and lower profits betwen 120 and 150:




2. Correct algorithm

Before trying to speed up the code, it's important to implement a correct algorithm (even if it is slow), otherwise it will be hard to check that the faster algorithm is correct.

In the general case, the problem of finding the highest profit is NP-hard, by an easy reduction from SUBSET SUM. But this isn't a disaster, because problems like subset sum often have pseudo-polynomial algorithms using the tabular method (aka "dynamic programming").

So let's try the tabular method by building up a table of prices, using \$−∞\$ for impossible amounts:

def buy_prices(buy_orders, limit):
    """Return array containing the best price for each amount below limit,
    given an array of buy orders. The result is -inf for any amount
    that cannot be sold to any combination of buy orders.

    """
    prices = np.full((limit,), -np.inf)
    prices[0] = 0
    for price, amount, min_amount in buy_orders:
        p = prices.copy()
        for a in range(int(min_amount), int(amount) + 1):
            for i in range(a, limit):
                prices[i] = max(prices[i], p[i-a] + a * price)
    return prices


This has runtime \$Θ(mn^2)\$, where \$m\$ is the number of buy orders and \$n\$ is the maximum amount that can be traded.

We can speed this up by vectorizing the inner loop:

def buy_prices(buy_orders, limit):
    """Return array containing the best price for each amount below limit,
    given an array of buy orders. The result is -inf for any amount
    that cannot be sold to any combination of buy orders.

    """
    prices = np.full((limit,), -np.inf)
    prices[0] = 0
    for price, amount, min_amount in buy_orders:
        p = prices.copy()
        for a in range(int(min_amount), min(limit, int(amount) + 1)):
            q = p[:limit-a] + a * price
            prices[a:limit] = np.maximum(prices[a:limit], q)
    return prices


However, the runtime is still \$Θ(mn^2)\$ and so it will be unacceptable when \$n\$ is large.