Maximizing profit for given stock quotes

问题:

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

回答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)

回答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]) );

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

回答4:

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


          }
   }

回答5:

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.

回答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!

回答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);
    }

回答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;
        }

回答9:

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;

}