title: Maximizing profit for given stock quotes
body: <p>I was asked this question while interviewing for a startup and saw this again in the recent contest at</p>
  <p><a href="https://systems.interviewstreet.com/challenges/" rel="nofollow noreferrer">Code Sprint:systems</a></p>
  <p>**The question  :</p>
  <p>You are given the stock prices for a set of days . Each day, you can either buy one unit of stock, sell any number of stock units you have already bought, or do nothing. What is the maximum profit you can obtain by planning your trading strategy optimally?**</p>
  <p>Examples ( The input  i.e the no of days can vary )</p>
  <p>5  3  2   =&gt; profit = 0 // since the price decreases each day ,the max profit we can make = 0</p>
  <p>1 2 100 =&gt; profit = 197</p>
  <p>1 3 1 2  =&gt;profit = 3   // we buy at 1 sell at 3 , then we buy at 1 and sell at 2 ..total profit = 3</p>
  <p>My Solution :</p>
  <p>a) Find the day when the stock price was largest . Keep buying 1 unit of stock till that day.</p>
  <p>b) If that day is the last day then  quit:</p>
  <p>else:
  Sell all the stocks on that day and split the array after that day and recurse on the remaining elements<br />
  c) merge the profits</p>
  <p>e.g 1 4 1 2 3<br />
  a) highest stock price on day 2 .. so we buy stock on day 1 and sell it on day 2 ( profit = 3 )   then we recurse on the remaining days : 1 2 3</p>
  <p>b) Max price is 3 ( on day 5) so we keep buying stock on day 3 and day 4 and sell on day 5 ( profit = ( 3*2 - 3 = 3 )</p>
  <p>c) Total profit = 3 + 3 = 6</p>
  <p>The complexity for this turns out to be O(n^2) . this solution passed 10 of the 11 cases but exceeded the time limit on a last test case (i.e the largest  input)</p>
  <p>Can anyone think of a more efficient solution to this problem? Is there a dynamic programming solution ?</p>