Maximum profit that can be obtained - Buying and Selling

Question

Say we have an accurate prediction of Messi’s prices for a period of N days. The prediction is given as a list in which p_i represents the player’s price in day i. Bob plans to make multiple, successive transactions during this period, but CAN’T have more than one Messi at a time, and therefore needs to sell him before buying him again.

Bob starts out with a limited budget B and can’t buy a Messi which costs more than he can afford. Of course, Bob can add to his budget any profit he gets from buying and selling his Messis. Luckily for him, some of the times he starts with a Messi from opening a random gift pack beforehand.

At the end Bob just wants to have as much profit as possible, and sell hist last Messi.

---

Input format :

On the first line of the input file, you will find 3 integers, N, B and M.

N represents the number of days for which Bob has a prediction of Messi’s price. B represents Bob’s initial budget. M can be either 0 or 1; 0 if Bob starts without an initial Messi to sell and 1 if he does start with an initial Messi to sell.

On the next line you will find N integers: p1, p2, … , pN, separated by a whitespace, in which pi, represents Messi’s price on day i.

---

Given testcases

Test 1

7 5 0

20 10 30 5 10 10 20

Correct answer : 15

Explanation : Bob starts with an initial budget of 5 and no initial Messi to sell. He cannot buy any Messi until his price drops to 5, so his profit is only (20-5) = 15

---

Test 2

7 0 1

20 10 50 80 60 20 10

Correct answer: 90

Explanation: Bob starts with an initial budget of 0 and one Messi to sell. Therefore he sells his initial Messi for 20, buys him back for 10 and sells him for 80, so his profit is 20 + (80-10) = 90

---

This problem was given to me in an interview and I haven't been able to produce a functioning solution. In the meantime I've found a few simpler variations on this problem such as Maximum profit by buying and selling a share at most twice , but I've been unsuccessful in understanding how to adapt the thinking to my problem.

So far I've only been able to come up with a brute force solution that goes way beyond the time restrictions I was given (0.1 seconds for C++, where 1 <= N <= 10^5).

I'm looking for a solution and a way of thinking about this kind of problem, I can't seem to find the right way to think about this.

Answer 1

We can use dynamic programming.

1. Let's define f0(i) as the maximum budget we can obtain if we don't have Messi at the beginning of the day i. Let f1(i) be the same value in case we've got him.

2. Base values for i = 0 depend on whether we have him at the very beginning or not.

3. The transitions go as follows:

   • We can go from i to i + 1 and do nothing

   • If we have Messi, we can sell him (setting f0(i + 1) = max(f0(i + 1), f1(i) + price(i)))

   • If we don't have him and our budget is big enough, we can buy him (doing f1(i + 1) = max(f1(i + 1), f0(i) - price(i)))

4. The answer is f0(n) (which mean that all days passed and we don't have him).

This solution clearly requires a linear amount of time and space, so any reasonable C++ implementation should fit your requirements.

Answer 2

First simplification of the problem is to convert the initial "gift" of Messi to an equal amount of money at the initial price of Messi. The user has a choice to either buy that Messi back or not at the beginning.

Afterwards, you would find the first price that's low enough for the user to buy a Messi, and discard every prediction before that. Then, find all the local minimal and local maximal of the predicted prices, and buy on all the minimals and sell on all the maximals, but remember not to buy back if the local minimal is the last prediction.

This should solve the problem in O(N).

EDIT: A local minimal or maximal can be found by the 2nd-degree difference of the sequence:

d[i] = p[i+1] - p[i]
d2[i] = d[i] - d[i-1]

If d2[i] > 0, then it's local minimal; if d2[i] < 0, then it's local maximal. Obviously there will be some boundary conditions that you need to take care of, but it shouldn't be too hard.

Answer 3

// input
long predictionLength;
long budget;
bool startWithMessi;
long prediction[MAX_PREDICTION_LENGTH];

// output
long profit;

ifstream fin;
fin.open( DATA_FILE_NAME );
fin >> predictionLength >> budget >> startWithMessi;
for( long day = 0; day < predictionLength; day++ )
  fin >> prediction[day];
fin.close();

long money = budget;
bool messi = startWithMessi;
long dayIndex = 0;
while( dayIndex < predictionLength )
{
  if( messi )
  {
    if( dayIndex == predictionLength - 1
      || prediction[dayIndex] > prediction[dayIndex + 1] )
    {
      money += prediction[dayIndex];
      messi = false;
    }
  }
  else
    if( dayIndex < predictionLength - 1
      && prediction[dayIndex] < prediction[dayIndex + 1]
      && money >= prediction[dayIndex] )
    {
      money -= prediction[dayIndex];
      messi = true;
    }
  dayIndex++;
}

profit = money - budget;

cout << profit << endl;