Interview question: Maximum multiple-sell profit

Question

I got a question on an algorithm question I got in an interview and I can't seem to figure it out. I understand how it should work, but can't get it sorted algorithmically.

So assume a firm trades oil barrels and is only able to retain one oil barrel at a time. Assume the company knows the price per barrel for each and every day in a year. So its passed into as an array. How can one write an algorithm to find when to buy and sell?

Here's an example for just 5 days for simplification: 70 74 73 72 76, for days Monday through Friday respectively.

The best thing to do here is to to buy on Monday (70) sell on Tuesday (74) and then buy on Thursday (72) and sell on Friday (76). Should that be approached recursively? I really want to solve this.

Thanks,

Answer 1

I assume you want to maximise your profit, right?

In that case, you just buy at local minima and sell at local maxima, which would be a simple linear search.

Actually, it is that simple. Proof:

Let's denote

p(i) ... the price of oil on day i
have(i) ... 1 if we retain the barrel overnight from day i to day i+1, 0 otherwise

have is only defined for i in [0, N-1]

now, if we buy on day k and sell on day l, we'd have

have(k) = 1
have(l) = 0
have(i) = 1 for k < i < l

the profit would be

p(l)-p(k) = sum over {i from k to l-1} (p(i+1)-p(i))

Let's denote

M(i) = max(p(i+1) - p(i), 0)

For all possible boolean functions have, we have

profit(have) = sum over {i where have(i)==1} (p(i+1) - p(i))
 <= sum over {i where have(i)==1} max(p(i+1) - p(i), 0)
 <= sum over {i where have(i)==1} M(i)
 <= sum over {i in [0, N-1]} M(i)

The second line comes from the fact that max(x, 0) >= x, the third is simple rewrite in terms of M(i), the fourth comes from M(i) >= 0.

Now, if we set have(i) == (p(i+1)>p(i)), it would have the same profit as above, which means it is maximal. Also, that means you buy at local minima and sell at local maxima.

Answer 2

Algorithm in O(N) time and O(1) space:

Starting at index 0
If you haven't bought an oil barrel:
    if price[i] < price[i + 1], buy at price[i]
    // if price[i] >= price[i + 1], you will never buy at price[i]
    // as price[i + 1] can bring you more money. So just wait...
If you have bought an oil barrel:
    if price[i] > price[i + 1], sell at price[i]
    // if price[i] <= price[i + 1], you will never sell at price[i]
    // as price[i + 1] can bring you more money. So just wait...

C++ implementation:

#include <iostream>
#include <vector>

int best_profit(const std::vector<int>& prices)
{
  bool buying = true;
  int buying_price = 0;
  int profit = 0;

  for(std::vector<int>::size_type i = 0; i < prices.size() - 1; ++i)
  {
    if(buying)
    {
      if(prices[i] < prices[i + 1])
      {
        buying_price = prices[i];
        buying = false;
      }
    }
    else if(prices[i] > prices[i + 1])
    {
      profit += prices[i] - buying_price;
      buying = true;
    }
  }

  if(!buying) // The last price is the highest one!
  {
    profit += prices[prices.size() - 1] - buying_price;
  }

  return profit;
}

int main()
{
  std::vector<int> prices1{1};
  std::vector<int> prices2{1, 2};
  std::vector<int> prices3{3, 2};
  std::vector<int> prices4{70, 74, 73, 72, 76};
  std::vector<int> prices5{70, 75, 71, 80, 96, 100, 15, 50, 60};

  std::cout << "prices1: " << best_profit(prices1) << std::endl;
  std::cout << "prices2: " << best_profit(prices2) << std::endl;
  std::cout << "prices3: " << best_profit(prices3) << std::endl;
  std::cout << "prices4: " << best_profit(prices4) << std::endl;
  std::cout << "prices5: " << best_profit(prices5) << std::endl;
}

Output:

prices1: 0
prices2: 1
prices3: 0
prices4: 8
prices5: 79

Answer 3

Sell at a local maxima, buy at a local minima. Treat the price before you start as infinity and after you end as zero.

Answer 4

Taking your example or barrel prices: [70, 74, 73, 72, 76].

From the given prices, I can compute the daily price change (i.e. today's price - previous day's price). The "price change array" in this case would be [4, -1, -1, 4].

In the "price change array", a positive number means price has increased and negative number means price has decreased compared to previous day.

The solution would be to find all contiguous sub-arrays out of the "price change array" which contain only positive numbers.

Using this idea, I have written below python code to print the pairs of buying and corresponding selling days:

barrel_price = [70, 74, 73, 72, 76]
trading_days = {} #dictionary for storing {buy_day: sell_day}
buy_day=0
sell_day=buy_day+1

while sell_day < len(barrel_price):
    if barrel_price[sell_day]-barrel_price[sell_day-1]>0:
        #don't sell if price is still increasing
        sell_day=sell_day+1
        trading_days[buy_day] = sell_day-1
    else:
        #don't buy if price is still decreasing
        buy_day=sell_day
        sell_day=buy_day+1

print trading_days

This prints "{0: 1, 3: 4}" For the first pair 0:1, i.e. buying day 0 and selling day 1, the corresponding prices are 70 and 74 in the barrel_price array. For the next pair 3:4, the corresponding buying price is 72 and selling price is 76.