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)

Can anyone think of a more efficient solution to this problem? Is there a dynamic programming solution ?

Solution 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)

Solution 2

Another way to look at it:
In pre-processing, for each element a[i] find a[j] s.t. j > i and it maximizes (a[j] - a[i])
so, the Best you can do for a price at a[i] is Buy at a[i] and Sell at a[j]. If there exists no a[j] s.t. a[j] > a[i] then a[i] is not a Buy point at all.

Preprocessing time: O(N)

S[N-1] = A[N-1];
for(int i=N-2; i>=0; --i)
       S[i] = max(A[i], S[i+1]);

Here, S[i] is the price at which you should sell a[i].

Summing up total Profit: O(N)

long long int Profit = 0;
    for(int i=0;i<N;++i)
          Profit += max(0,  (S[i]-A[i]) );

Solution 3

Another O(n) solution for this task can be done by using local minimum and maximum finding the best deference (profit) between max and min knowing that max should have greater index then min. We also need to look at previous best local min (C# implementation).

public int[] GetBestShareBuyingStrategy(int[] price)
    {
        var n = price.Length;
        if (n <= 1)
            return null;

        var profit = 0;
        var min = 0;
        var max = 0;
        var lmin = 0;

        for (var i = 1; i < n; i++)
        {
            var lmax = i;
            var lp = price[lmax] - price[lmin];
            if (lp <= 0)
            {
                lmin = i;
            }
            else
            {
                var tp = price[lmax] - price[min];
                if (lp > tp && lp > profit)
                {
                    min = lmin;
                    max = lmax;
                    profit = lp;
                }
                else if (tp > profit)
                {
                    max = lmax;
                    profit = tp;
                }
            }
        }

        return profit > 0
            ? new [] {min, max}
            : null;
    }



    [Test]
    [TestCase(new[] { 10, 9, 8, 7, 3 })]
    [TestCase(new[] { 5, 5, 5, 5, 5 })]
    [TestCase(new[] { 5, 4, 4, 4 })]
    [TestCase(new[] { 5, 5, 3, 3 })]
    public void GetBestShareBuyingStrategy_When_no_sense_to_buy(int[] sharePrices)
    {
        var resultStrategy = GetBestShareBuyingStrategy(sharePrices);
        Assert.IsNull(resultStrategy);
    }

    [Test]
    [TestCase(new[] { 10, 8, 12, 20, 10 }, 1, 3)]
    [TestCase(new[] { 5, 8, 12, 20, 30 }, 0, 4)]
    [TestCase(new[] { 10, 8, 2, 20, 10 }, 2, 3)]
    [TestCase(new[] { 10, 8, 2, 20, 10 }, 2, 3)]
    [TestCase(new[] { 10, 2, 8, 1, 15, 20, 10, 22 }, 3, 7)]
    [TestCase(new[] { 1, 5, 2, 7, 3, 9, 8, 7 }, 0, 5)]
    [TestCase(new[] { 3, 5, 2, 7, 3, 9, 8, 7 }, 2, 5)]
    public void GetBestShareBuyingStrategy_PositiveStrategy(int[] sharePrices, int buyOn, int sellOn)
    {
        var resultStrategy = GetBestShareBuyingStrategy(sharePrices);
        Assert.AreEqual(buyOn, resultStrategy[0]);
        Assert.AreEqual(sellOn, resultStrategy[1]);
    }

Solution 4

I just solved that problem in a contest site. I think I got a simpler algorithm than the accepted answer.

1. smax = maximum stock price from the list
2. then find the profit by assuming you have bought all the stocks till smax 
   and you sell it at the price of smax
3. then check if smax is the last element of the stock price list 
   if yes then return profit as answer, 
   if no 
   then make a new list containing stock prices after smax to the last stock price
   and repeat steps 1-3 and keep adding profit of each iteration to get the final profit.

Solution 5

0.Start from end of array so that no need to recurse
1. smax = maximum stock price from the list
2.Then find the profit by assuming you have bought all the stocks till smax and you sell it at the price of smax

          public static void main(String[] args) {

          Scanner sc = new Scanner(System.in);
          int numOfTestCase = sc.nextInt();
          for (int i = 0; i < numOfTestCase; i++) {
                 int n = sc.nextInt();
                 long profit = 0;
                 int[] stockPrice = new int[n];

                 for (int j = 0; j < n; j++) {
                       stockPrice[j] = sc.nextInt();
                 }

                 int currMax = Integer.MIN_VALUE;

                 for (int j = n - 1; j >= 0; j--) {
                       if (currMax < stockPrice[j]) {
                              currMax = stockPrice[j];
                       }
                       profit += (currMax - stockPrice[j]);
                 }
                 System.out.println(profit);


          }
   }

View more solutions

Comments

[Johan Lundberg]

for each element a[i] find a[j] s.t. j > i How is this O(n) ? Is that not O(n^2) ?

[srbhkmr]

We can process that information in O(N) itself. (I've updated my post.) I think your solution and mine are same. Its just I'm trying to visualize it from the beginning, that's all.

[Johan Lundberg]

Just explain how you do for each a[i] find a[j] s.t. j > i for a i in linear access.

[srbhkmr]

What do you mean by "now also"? I already posted that the pre-processing (getting the optimal sell price for each point) can be done in O(N) time.

[Mateusz Dymczyk]

is the max() function necessary while summing up the profit? S[i] is always larger than or equal to A[i] therefore you always get max(0,0) or (0, something_bigger_than_0). And as you pointed out it is exactly the same solution as Johan's but requires extra O(n) space.

[smohamed]

In theory, this problem is listed under "dynamic programming" what is exactly has to do with dynamic programming here? if you can explain the relation I would be grateful.

[craftsmannadeem]

'calcprofit([1,2,100]) gives (197, [1, 1, 0])' : kind of curious how can profit be 197

[Johan Lundberg]

@craftsmannadeem: first get one stock for 1$, then another one for 2$, then sell the two stocks at $100 each.

[Alex]

if the last value is highest, then all trading opportunities in between would be missed, example calcprofit([1,2,3,1,2,3,1,2,3,4]) gives (18, [1, 1, 1, 1, 1, 1, 1, 1, 1, 0])

[Johan Lundberg]

@alex true, but the question posted is not about that kind of strategies: The question has an explicit constraint that you buy at most one stock each day (check the original questions examples also). My answer correctly solves the problem in question but as you state, there are better strategies.