algorithm - Maximizing profit for given stock quotes

Question

I was asked this question while interviewing for a startup and saw this again in the recent contest at

Code Sprint:systems

**The question :

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?**

Examples ( The input i.e the no of days can vary )

5 3 2 => profit = 0 // since the price decreases each day ,the max profit we can make = 0

1 2 100 => profit = 197

1 3 1 2 =>profit = 3 // we buy at 1 sell at 3 , then we buy at 1 and sell at 2 ..total profit = 3

My Solution :

a) Find the day when the stock price was largest . Keep buying 1 unit of stock till that day.

b) If that day is the last day then quit:

else: Sell all the stocks on that day and split the array after that day and recurse on the remaining elements
c) merge the profits

e.g 1 4 1 2 3
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

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 )

c) Total profit = 3 + 3 = 6

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)

So my question is can anyone think of a more efficient solution to this problem ? Is there a dynamic programming solution ?

P.S: this is the first time i am asking a question here. so please let me know if i need to improve/add things to this question

Answer 1

I agree with the logic of your method but there is no need to do recursive processing or global maxima searches. To find the sell/buy days you just need to look at each day once:

The trick is to start from the end. Stock trade is easy if your travel backwards in time!

If you think code is easier to read than words, just skip my explanation, but here goes:

Reading from the end, look at price of that day. Is this the highest price so far (from the end), then sell! The last day (where we start reading) you will always sell.

Then go to the next day (remember, backwards in time). Is it the highest price so far (from all we looked at yet)? - Then sell all, you will not find a better day. Else the prices increase, so buy. continue the same way until the beginning.

The whole problem is solved with one single reverse loop: calculating both the decisions and the profit of the trade.

Here's the code in C-like python: (I avoided most pythonic stuff. Should be readable for a C person)

def calcprofit(stockvalues): 
    dobuy=[1]*len(stockvalues) # 1 for buy, 0 for sell
    prof=0
    m=0
    for i in reversed(range(len(stockvalues))):
        ai=stockvalues[i] # shorthand name
        if m<=ai:
            dobuy[i]=0
            m=ai
        prof+=m-ai
    return (prof,dobuy)  

Examples:

calcprofit([1,3,1,2]) gives (3, [1, 0, 1, 0])
calcprofit([1,2,100]) gives (197, [1, 1, 0])
calcprofit([5,3,2])   gives (0, [0, 0, 0])
calcprofit([31,312,3,35,33,3,44,123,126,2,4,1]) gives
 (798, [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0])

Note that m is the highest stock price we have seen (from the end). If ai==m then the profit from stocks bought at the the step is 0: we had decreasing or stable price after that point and did not buy.

You can verify that the profit calculation is correct with a simple loop (for simplicity imagine it's within the above function)

stock=0
money=0
for i in range(len(stockvalues)):  
    if dobuy[i]:
        stock+=1
        money-=stockvalues[i]
    else:
        money+=stockvalues[i]*stock
        stock=0
print("profit was: ",money)