title: Maximum profit that can be obtained - Buying and Selling
body: <p>Say we have an accurate prediction  of Messi’s prices for a period of <code>N</code> days. The prediction is given as a list in which <code>p_i</code> represents the player’s price in day <code>i</code>. 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.</p>
  
  <p>Bob starts out with a limited budget <code>B</code> 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.</p>
  
  <p>At the end Bob just wants to have as much profit as possible, and sell hist last Messi.</p>
  
  <hr>
  
  <p><strong>Input format :</strong></p>
  
  <p>On the first line of the input file, you will find 3 integers, N, B and M.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <hr>
  
  <p><strong>Given testcases</strong></p>
  
  <p><strong>Test 1</strong></p>
  
  <p>7 5 0</p>
  
  <p>20 10 30 5 10 10 20</p>
  
  <p><strong>Correct answer : 15</strong></p>
  
  <p>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</p>
  
  <hr>
  
  <p><strong>Test 2</strong></p>
  
  <p>7 0 1</p>
  
  <p>20 10 50 80 60 20 10</p>
  
  <p><strong>Correct answer: 90</strong></p>
  
  <p>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</p>
  
  <hr>
  
  <p>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 <a href="http://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-twice/" rel="nofollow noreferrer">Maximum profit by buying and selling a share at most twice</a> , but I've been unsuccessful in understanding how to adapt the thinking to my problem.</p>
  
  <p>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 &lt;= N &lt;= 10^5). </p>
  
  <p>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.</p>