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)

Answer 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]) );

Answer 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]);
    }

Answer 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.

Answer 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);


          }
   }

Answer 6

your logic is correct...

sell at global maxima's..but recursion is not required...

if ith element is global maxima...sell all stocks before i!

Now problem reduces to previous answer+ i+1 to N...

recursion is not required...linearly we can calculate!

Answer 7

here is more simple and easy to understand algo;

    private static void BuyOnceAndSellONce()
    {
        int[] stock = new int[] { 100, 180, 260, 310, 40, 535, 695 };
        int profit = 0;
        int minimumPrice = int.MaxValue;
        for (int i = 0; i < stock.Length; i++)
        {
            profit = Math.Max(profit, stock[i] - minimumPrice);
            minimumPrice = Math.Min(stock[i], minimumPrice);

        }
        Console.WriteLine("profit "  + profit);
    }

    private static void MultipleBuySellButNonOverlappingTransactions()
    {
        int[] stock = new int[] { 100, 180, 260, 310, 40, 535, 695 };
        int totalProfit = 0;
        int currentProfit = 0;
        for (int i = 1; i < stock.Length;i++)
        {
            currentProfit = stock[i] - stock[i - 1];
            if (currentProfit > 0)
                totalProfit += currentProfit;
        }

        Console.WriteLine(totalProfit);
    }

Answer 8

private static int MaxProfit(int[] A)
        {
            if (A.Length == 0)
                return 0;
            Stack<int> repositoryStack = new Stack<int>();
            int maxProfit = 0;
            int tempProfit;
            for (int i = 0; i < A.Length; i++)
            {
                if (repositoryStack.Count == 0)
                {
                    repositoryStack.Push(i);
                    continue;
                }
                while (repositoryStack.Count != 0 && A[i] < A[repositoryStack.Peek()])
                {
                    repositoryStack.Pop();
                }
                if (repositoryStack.Count != 0 && A[i] > A[repositoryStack.Peek()])
                {
                    tempProfit = A[i] - A[repositoryStack.Peek()];
                    if (tempProfit > maxProfit)
                        maxProfit = tempProfit;
                }
                if(repositoryStack.Count == 0)
                    repositoryStack.Push(i);
            }
            return maxProfit;
        }

Answer 9

I was able to find a simple solution on O(n) time complexity.

Below is the code for it:

/** 
* 
* @author techieExpress 
* 
* The cost of a stock on each day is given in an array, 
* find the max profit that you can make by buying and selling in those days.  
* For example, if the given array is {100, 180, 260, 310, 40, 535, 695},  
* the maximum profit can earned by buying on day 0, selling on day 3.  
* Again buy on day 4 and sell on day 6.  
* If the given array of prices is sorted in decreasing order,  
* then profit cannot be earned at all. 
*  
* 
* YouTube video explanation link - https://youtu.be/IYENA3WpwsA 
**/ 
import java.util.ArrayList; 
//Solution structure 
class Interval { 
    int buy, sell; 
} 
public class stockBuySell { 
    // This function finds the buy sell schedule for maximum profit 
    // { 100,50, 180, 260, 310, 40, 535, 695 } ,n=7 
    public void stockBuySell(int price[], int n) { 
        // Prices must be given for at least two days 
        if (n < 2) 
            return; 
        int count = 0; 
        // solution array 
        ArrayList<Interval> sol = new ArrayList<Interval>(); 
        // Traverse through given price array 
        int i = 0; 
        while (i < n - 1) { 
            // Find Local Minima. Note that the limit is (n-2) as we are 
            // comparing present element to the next element. 
            while ((i < n - 1) && (price[i ] >= price[i+1])) 
            i++; 
            // If we reached the end, break as no further solution possible 
            if (i == n - 1) 
                break; 
            Interval e = new Interval(); 
            // Store the index of minima 
            e.buy = i; 
            i++; 
            // Find Local Maxima. Note that the limit is (n-1) as we are 
            // comparing to previous element 
            while ((i < n) && (price[i] >= price[i - 1])) 
                i++; 
            // Store the index of maxima 
            e.sell = i - 1; 
            sol.add(e); 
            // Increment number of buy/sell 
            count++; 
        } 
        // print solution 
        if (count == 0) 
            System.out.println("There is no day when buying the stock " + "will make profit"); 
        else 
            for (int j = 0; j < count; j++) 
                System.out.println("Buy on day: " + sol.get(j).buy + " " + "Sell on day : " + sol.get(j).sell); 
        return; 
    } 
    public static void main(String args[]) { 
        // stock prices on consecutive days 
        int price[] = { 100,50,130,140,40,20,200,30,10 }; 
        int n = price.length; 
        stockBuySell stock = new stockBuySell(); 
        stock.stockBuySell(price, n); 
    } 
} 

Git link for code: https://github.com/TechieExpress/Data...

If you want to understand the underlying concept used, you can watch out the detailed explanation on TechieExpress youtube channel video - https://youtu.be/kA6O1laqrvY

Answer 10

My reasoning is, you make profit for every stock bought before the maximum stock price. Using this line of thought, you buy every stock before the maximum price, sell it at the maximum, and repeat the same thing for the remaining stock prices.

function profit(prices){
    var totalStocks = 0, profitMade = 0;

    var buySell = function(sortedPrices){
        for(var i = 0, len = sortedPrices.length; i < len; i++){
            if (i < len - 1){
                totalStocks++;
                profitMade = profitMade - sortedPrices[i];
            }else{
                profitMade = profitMade + totalStocks * sortedPrices[i];
                totalStocks = 0;
            }
        }
    }, splitMaxPrice = function(rawPrices){
        var leftStocks = rawPrices.splice(rawPrices.lastIndexOf(Math.max.apply(null, rawPrices))+1);
        buySell(rawPrices);
        if(leftStocks.length > 0){
            splitMaxPrice(leftStocks);
        }
        return;
    };

    splitMaxPrice(prices);

    return profitMade;

}