Find buy/sell prices in array of stock values to maximize positive difference

Question

Got this question in an interview today, and its optimized solution stopped me cold (which blows, because I really wanted to work for this company...)

Given a single array of real values, each of which represents the stock value of a company after an arbitrary period of time, find the best buy price and its corresponding best sell price (buy low, sell high).

To illustrate with an example, let's take the stock ticker of Company Z:

55.39 109.23 48.29 81.59 105.53 94.45 12.24

Important to note is the fact that the array is "sorted" temporally - i.e. as time passes, values are appended to the right end of the array. Thus, our buy value will be (has to be) to the left of our sell value.

(in the above example, the ideal solution is to buy at 48.29 and sell at 105.53)

I came up with the naive solution easily enough with O(n²) complexity (implemented in java):

// returns a 2-element array: first element is the index in the argument array
// of the best buying price, and the second element is the index of the best
// selling price which, collectively, maximize the trading return
//
// if there is no favorable trading (e.g. prices monotonically fall), null is returned
public int[] maximizeReturn(ArrayList<Double> prices) {
  int [] retval = new int[2];
  int BUY = 0, SELL = 1;
  retval[BUY] = retval[SELL] = -1; // indices of buy and sell prices, respectively

  for (int i = 0; i < prices.size(); i++) {
    for (int j = i + 1; j < prices.size(); j++) {
      double difference = prices.get(j).doubleValue() - 
                          prices.get(i).doubleValue();

      if (difference > 0.0) {
        if (retval[BUY] < 0 || difference > prices.get(retval[SELL]).doubleValue() - 
                                            prices.get(retval[BUY]).doubleValue()) {
          retval[BUY] = i;
          retval[SELL] = j;
        }
      }
    }
  }
  return (retval[BUY] > 0 ? retval : null);
}

Here's where I screwed up: there's a linear time O(n) solution, and I completely bombed in trying to figure it out (yeah, I know, FAIL). Does anyone know how to implement the linear time solution? (any language you're comfortable with) Thanks!

Edit

I suppose, for anyone interested, I just received word today that I didn't get the job for which I interviewed where they asked me this question. :(

Buckjumper

I'd like to see some functional implementations of this... strikes me of the sort of thing functional people do nicely in a tricky way... – Sunn

I'd bet you interviewed at Bloomberg, eh? – Fasano

Good job outta you, don't worry about the job, job interviews are fickle and really do not measure real world performance very well – Midsection

Answer 1

Here's an attempt (C++). Basically everytime I track a new top, I try to see if thats the best profit thusfar. I know that the "bottom" must have been discovered earlier. At that point I remember the top, bottom, and the current max profit. If a new bottom is discovered later, its AFTER the current top, so we must reset top and see if a slightly lower "top" can yield better profit.

#include <iostream>

int main()
{

    double REALLY_BIG_NO = 1e99;
    double bottom = REALLY_BIG_NO; // arbirtrary large number
    double currBestBuy = 0.0;
    double top = 0.0;
    double currBestSell = 0.0;
    double profit = 0.0;

    // array of prices
    double prices[] = {10.50, 55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24, 152.0, 2, 170.0};
    int numPrices = 10;// number of prices

    for (int i = 0; i < numPrices; ++i)
    {
         if (prices[i] < bottom)
         {
            bottom = prices[i];
            // reset the search on a new bottom
            top = 0.0;
         }
         else if (prices[i] > top)
         {
            top = prices[i];
           // calculate profit
            double potentialProfit = (top - bottom);
            if (potentialProfit > profit &&
                bottom != REALLY_BIG_NO)
            {
                profit = potentialProfit;
                currBestSell = top;
                currBestBuy = bottom;
            }
         }
    }

    std::cout << "Best Buy: " << currBestBuy << "Best Sell: " << currBestSell << std::endl;
}

So far I've played around with a bunch of different input sets, and so far I haven't had any problems... (let me know if you test this and see anything wrong)

I highly recommend using Austin Salonen's updated answer to this question and adapting it to your language.

Maziemazlack

I was inching close to a solution like this one as I bumbled along; I had five variables set up exactly as you do. Unfortunately I started doing some crazy value swapping and pretty much went off the deep end from there. =/ – Buckjumper

I rebuilt my algo and it's the same as yours now... Different language and some really good comments so I'll leave it up. – Universe

This doesn't work when you swap 152.0 and 170.0 (i.e when stocks = {10.50, 55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24, 170.0, 2, 152.0}; – Phototelegraphy

Answer 2

In C#:

static void Main(string[] args)
{
    double[] values = new double[7]{55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24};

    double max = double.MinValue, maxDiff = double.MinValue, diff = 0;

    for (int i = 1; i < values.Length; i++)
    {
        if (values[i] > values[i - 1])
        {
            //trending upward, append to existing differential
            diff += values[i] - values[i - 1];
        }
        else
        {
            //trending downward, reset the diff
            diff = 0;
        }

        if (diff > maxDiff)
        {
            maxDiff = diff;
            max = values[i];
        }
    }

    Console.WriteLine("Buy at {0}; Sell at {1}", max - maxDiff, max);
}

EDIT: New algo based on @Joe's failing test case -- Nice Catch BTW! It's also the same answer as @Doug T's now...

static void Main(string[] args)
{
    double[] values = new double[8] { 55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24 };

    double max = double.MinValue, maxDiff = double.MinValue, diff = 0;
    double bottom = values[0];

    for (int i = 1; i < values.Length; i++)
    {
        diff += values[i] - values[i - 1];

        if (diff > maxDiff)
        {
            maxDiff = diff;
            max = values[i];
        }

        if (values[i] < bottom)
        {
            bottom = values[i];
            diff = 0;
        }
    }

    Console.WriteLine("Buy at {0}; Sell at {1}", max - maxDiff, max);
}

Universe

I suppose there should be a check that max & maxDiff were actually set before displaying them (for a sorted descending list) but we'll be optimistic the stock had at least one good session... – Universe

I really like this; the idea of incrementing the differential hadn't occurred to me. Very elegant! – Buckjumper

This seems to fail for the input 55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24 ? Best is still to buy at 48.29 and sell at 105.53 (57.24 profit), but it says to buy at 55.39 and sell at 109.23 (53.84 profit) – Decahedron

Yup, small dips confuse this algo. – Venomous

Actually yes this solution seems to have a flaw whereby if you trend downward then immediately back up again, but the bottom was before you trended downward, your diff is reset and you won't see the opportunity... – Maziemazlack

Yeah I guess you can't just track diffs because you have to know at any given time where the global minimum is... damn I thought you were onto something really a lot more elegant than my solution. Maybe you are, and there's a quick fix? – Maziemazlack

I left the original code in the answer so the comments make sense. – Universe

Very nice, glad to see you could find an answer. – Maziemazlack

Answer 3

The idea is simple. Keep two pointers, lo and hi.
Do a Foor loop

1. if price is higher than hi, update hi = price, continue
2. if the price is lower than hi. Then lo and hi is one of possible candidates. Calculate the profit, store it if it's bigger than previous profits and reset lo, hi to price

def getBestProfit(prices):
    lo = hi = profit = 0

    for price in prices:
        if lo == 0 and hi == 0:
            lo = hi = price

        if price > hi:
            hi = price

        if price < low:
            tmpProfit = hi - lo
            if tmpProfit > profit:
                profit = tmpProfit

            lo = hi = price
    return profit

That's it

Auberon

Answer 4

void getBestTime (int stocks[], int sz, int &buy, int &sell){
int min = 0;
int maxDiff = 0;
buy = sell = 0;
for (int i = 0; i < sz; i++) 
{
    if (stocks[i] < stocks[min])
    {
        min = i;
    }
    int diff = stocks[i] - stocks[min];
    if (diff > maxDiff) 
    {
        buy = min;
        sell = i;
        maxDiff = diff;
    }
}}

Just in case you prefer this answer. I found it in another web, but still. source:http://leetcode.com/2010/11/best-time-to-buy-and-sell-stock.html

Gardening

Answer 5

      public void profit(float stock[], int arlen ){
            float buy = stock[0];
            float sell = stock[arlen-1];
            int bi = 0;
            int si = arlen - 1;

            for( int i = 0; i < arlen && bi < si ; i++){

                    if( stock[i] <  buy && i < si){
                            buy = stock[i];
                            bi = i;
                    }
                    if(stock[arlen - i - 1] > sell &&  (arlen - i -1)  > bi){
                            sell = stock[arlen - i - 1];
                            si = arlen - i - 1;
                    }
            }
            System.out.println(buy+" "+sell);
    }

Revamp

Answer 6

I really have to point out as an interview question expecting you to solve it as O(n) is borderline absurd. Interview questions are meant to prove you can solve a problem, which you were able to solve it. The fact you solved it in O(N^2) vs O(N) should be irrelevant. If a company would pass over hiring you for not solving this in O(N) that's probably not a company you would have wanted to work at anyway.

Hultin

"The fact you solved it in O(N^2) vs O(N) should be irrelevant." - I really hope you are right on this one :) – Buckjumper

well as an interviewer, its often useful to push interviewees. All else being equal, if only 1 position is open, given the choice between the O(n) solver and the O(n^2) solver, I'll take the O(n) solver. That being said, I'm glad when I interview someone these days that knows O(n) from O(n^2) so you'd probably get the job where I work! – Maziemazlack

@Doug, the issue is about solving the problem first. Unless we're talking N into *illions for a modern computer the difference from linear and binomial time should be negligible. This also goes with avoid early optimization, if they asked a question that could be solved with recursion easily is it better to use the elegant method or to spend the time to write it so it can be done in a loop instead of recursively before it's needed? Optimization can always be done later. – Hultin

Having been the interviewer, I'd say that posing this question is a great tool: 1) if they can't code even the O(n^2) solution, they're not a programmer. 2) If they've seen the O(n) solution, that just means they've done a lot of reading (it's really an obscure 'AHA' kind of question). 3) If they haven't, then walking through the thought process of trying to find it should be very illuminating. – Venomous

You know nothing at all about the position, and what kinds of challenges the employee will face. Perhaps for this job the most important skill is minimizing the Order of algorithms, because of the large size of their data and the low latency demands for computation. And perhaps that kind of job is at exactly the kind of company the OP wants to work for. How can you assert which skills "should be irrelevant" to any given company, and any given position? Let alone which people will think a company is "not a company [they] would have wanted to work at anyway"? – So

@MattCruikshank it's not the place to blindside a candidate with that specificity of questioning in an interview. if you want that level of detail, the time for this is in preparation for the interview. Provide the candidate the inefficient algorithm and explain to them their goals and provide them a fair amount of time to do so. It is unconscionably rude to spring this on a person. When it comes to algorithms for the most part you spend more time researching than you do writing code. At the minimum, existing work should be used for reference if not solve the problem. CS problems arent new – Hultin

@ChrisMarisic, again it depends entirely upon the job. If the job is to improve inefficient code that others have written, all day long, every day, that's one thing. Look, I'm not arguing that EVERY interview should have this question. I can't believe you're telling me that NO interview can have this question. – So

@ChrisMarisic - I've had recruiters tell me a specific book to master, before interviewing - and I did, and it was tested fairly in the in-person interview - and I got the job. I've had other interviews where it was obvious from the Required and Recommended skills listed for the opening that I was supposed to bone up on OpenGL, or on Image Processing, or on Python, before showing up. You're the one presuming A) blindsiding, and B) that the job function wouldn't require this kind of skill. – So

Answer 7

I'd like to describe how I approached this problem to make it easier to understand my code:

(1) For each day, if I had to sell my stock on that day, what would be the minimum amount I could have paid to buy it? Essentially, I'm keeping track of minimum price before that day

(2) For each day, if I were to sell on that day, how much am I earning? (Stock price on that day - minimum price)

This shows that I have to keep track of two things: (1) minimum stock price so far (2) best earning so far.

The problem becomes choosing which day to sell. I will sell on the day that will give me the best earning. Here is my Java code:

    public static void findBestDeal(double [] stocks) {
    double minsofar = stocks[0];
    double bestsofar = 0.0;

    for(int i=1; i< stocks.length; i++) {

        // What is the cheapest price to buy it if I'm going to sell it today
        if(stocks[i-1] < minsofar) {
            minsofar = stocks[i-1];
        }

        // How much do I earn if I sell it on ith day?
        double current_deal = stocks[i] - minsofar;

        // Is selling today better?
        if(current_deal > bestsofar) {
            bestsofar = current_deal;
        }
    }

    System.out.println("Found the best deal: " + bestsofar + " (Bought at " + minsofar + " and sold at " + (minsofar+bestsofar) + ")");

}

Infanticide

Answer 8

Here is my O(n) implementation for this. I am using a change array to calculate the max profit and buy and sell dates. Your comments on this are welcome.

#include<stdafx.h>
#include<stdio.h>

int main()
{
    //int arr[10] = {15, 3, 5,9,10,1,6,4,7,2};
    int arr[7] = {55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24};
    int change[7];
    int n=7;
    for(int i=1;i<=n;i++)
    {
    change[i] = arr[i]- arr[i-1];
    }
    int i=0,index = 0;
    int sum = 0;
    int maxsum = 0;
    int startpos = 0;
    int endpos = 0;
    while(index < n)
    {
        sum = sum + change[index];
        if(maxsum < sum)
        {
        maxsum = sum; 
        startpos = i;
        endpos = index;

        }
        else if (sum<0) // negative number ,set sum to zero
        {
        sum = 0;
        i=index+1;
        }
        index++;
    }

    printf("max profit is%d %d %d", maxsum , startpos, endpos+1 );
}

Abebi

Answer 9

In my effort to learn Go, and also to rake my brain on this one, here is my attempt.

func GetMaxProfit2(prices []float64) (float64, float64) {
    var min, max, pmin, pmax int

    for i, v := range prices {
        if v - prices[min] > prices[max] - prices[min] {
            pmax = max
            max = i
        }
        // Reset the max when min is updated.
        if v < prices[min] {
            pmin = min
            min = i
            pmax = max
            max = i
        }
    }

    // If min is ahead of max, reset the values back    
    if min >= max {
        min = pmin
        max = pmax
    }

    return prices[min], prices[max]
}

Leonie

Answer 10

Here is my attempt using Javascript. The script computes the answer in O(N):

//Main Stock Array
var stock = [15, 20, 0, 3, 30, 45, 67, 92, 1, 4, 99];


//Setup initial variable state
var ans = {}, tmp = {}; //These are just for namespacing / syntatic sugar
ans.minVal = stock[0];
ans.minInd = 0;
ans.maxDiff = stock[1] - stock[0];
ans.maxInd = 1;
tmp.minInd = ans.minInd;
tmp.minVal = ans.minVal;

//Basically we iterate throught the array. If we find a new low, we start tracking it. Otherwise we compare the current index against the previously found low
for(i = 1; i <= stock.length-1; i++) {
    if(tmp.minVal > stock[i]) {
        tmp.minVal = stock[i];
        tmp.minInd = i;
    } else {
        ans.diff = stock[i] - stock[tmp.minInd];
        if(ans.diff > ans.maxDiff) { //Looks like we found a new maxDifference. Lets log the indexes
            ans.maxDiff = ans.diff;
            ans.maxInd = i;
            ans.minInd = tmp.minInd;
            ans.minVal = tmp.minVal;
        }
    }
}

document.write('You should buy your stocks on day ' + ans.minInd + ' and sell on day ' + ans.maxInd);

Perspicacity

Answer 11

This is a C solution that actually works:

void bestBuySell() { double prices[] = {10.50, 10.0, 3.0, 194.0, 55.39, 2.0, 109.23, 48.29, 81.59, 105.53, 94.45, 191.0, 200.0, 12.24}; int arrSize = 14; double bestBuy = prices[0], bestSell = prices[1], bestPotentialBuy = prices[0]; double potentialProfit = prices[1] - prices[0];

for(int i = 1; i < (arrSize-1); i++)
{
    if(prices[i] < bestBuy)
        bestPotentialBuy = prices[i];            

    if((prices[i+1] - bestPotentialBuy) > potentialProfit)
    {
        bestBuy = bestPotentialBuy;
        bestSell = prices[i+1];
        potentialProfit = prices[i+1] - bestPotentialBuy;
    }
}

printf( "bestBuy %f bestSell %f\n", bestBuy, bestSell );

}

Keynote

Answer 12

1.We cant simply take the least amount among the values as " Best Buy" and the max amount as "Best Sell" because "Sell" has to happen after "Buy".

2.We must not treat the recorded minimum as the "Best Buy" because the subsequent days may have stock values whose difference with the recorded minimum may yield profit which could be less than the "recorded profit".

3.Best Buy and Best Sell is treated as a single variant,because it is the positive difference between these values that makes max profit.

4.Since any recorded minimum in the past is a potential candidate for buying,the max profit condition must always be checked against the recorded minimum and the current day's stock price.So we always have to keep track of recorded minimum,but just the presence of recorded minimum doesn't constitute "Best Buy" because of reason number 2.

Now have the below code which executes in O(n) times will make sense.

public class BestStockBuyAndSell {

public static void main(String[] args) {

    double[] stockPrices = {55.39,109.23,48.29,81.59,105.53,94.45,12.24};
    int [] bestBuySellIndex = maxProfit(stockPrices);

    System.out.println("Best Buy At "+stockPrices[bestBuySellIndex[0]]);
    System.out.println("Best Sell At "+stockPrices[bestBuySellIndex[1]]);

    System.out.println("Max Profit = "+(stockPrices[bestBuySellIndex[1]]-stockPrices[bestBuySellIndex[0]]));

}

public static int[] maxProfit(double[] stockPrices)
{
    int bestBuy=0;
    int bestSell=0;

    int[] bestCombination ={bestBuy,bestSell};
    double recordedMinimum = stockPrices[bestBuy];
    int recordedMinimuIndex = bestBuy;
    double bestProfitSofar = stockPrices[bestSell] - stockPrices[bestBuy];

    for(int i=1;i<stockPrices.length;i++)
    {
        if(stockPrices[i] - recordedMinimum > bestProfitSofar)
        {

            bestProfitSofar = stockPrices[i] - recordedMinimum;
            bestSell = i;
            bestBuy = recordedMinimuIndex;
        }

        if(stockPrices[i] < recordedMinimum)
        {
            recordedMinimuIndex = i;
            recordedMinimum = stockPrices[i];
        }

    }

    bestCombination[0] = bestBuy;
    bestCombination[1] = bestSell;


    return bestCombination;

}

}

Sporocarp

Answer 13

I came up with following algorithm for this problem, seems to work for all inputs. Also, If the Stock value keeps droping, the program would output not to buy this stock:

  public class GetMaxProfit 
  { 

  double minValue = -1, maxValue = -1;
  double maxDiff = 0;

  public void getProfit(double [] inputArray){
    int i=0, j=1;
    double newDiff = 0;
    while(j<inputArray.length){
         newDiff = inputArray[j]-inputArray[i];
         if(newDiff > 0){
             if(newDiff > this.maxDiff){
               this.minValue = inputArray[i];
               this.maxValue = inputArray[j];
               this.maxDiff = newDiff;
             }
        }
        else{
            i = j;
        }
        j++;
    }
 }

 public static void main(String[] args) {
    // TODO Auto-generated method stub
    GetMaxProfit obj = new GetMaxProfit();

    obj.getProfit(new double[]{55.39, 19.23, 14.29, 11.59, 10.53, 9.45, 1.24});
    if(obj.minValue != -1 && obj.maxValue != -1){
      System.out.println("Buy Value for the input: "+obj.minValue);
      System.out.println("Sell Value for the input: "+obj.maxValue);
      System.out.println("Best profit for the input: "+obj.maxDiff);
            }
            else
               System.out.println("Do Not Buy This STOCK!!);

 }

}

Is there any catch you could find in this? It's time complexity is O(N)

Clipclop

Answer 14

Here is my solution, same as @Doug T. except I am also keeping track of the day in an index. Please provide feedback.

 int prices[] = {4,4,5,6,2,5,1,1};
 //int prices[] = {100, 180, 260, 310, 40, 535, 695};

 int currentBestSellPrice=0;
 int currentBestBuyPrice=0;
 int lowindex=0;
 int highindex=0;
 int low=prices[0];
 int high=prices[0];
 int profit=0;
 int templowindex=0;
 for(int i=0; i< prices.length;i++)
 {
     // buy low
     if(prices[i] < low && i+1 < prices.length)
     {
         low = prices[i];  
         templowindex=i;
         high=0;
     }
     // sell high
     else if(prices[i] > high)
     {
         high = prices[i];
         int potentialprofit = (high-low);
         if(potentialprofit > profit)
         {
             profit = potentialprofit;
             currentBestSellPrice = high;
             currentBestBuyPrice = low;
             highindex=i;
             lowindex=templowindex;
         }
     }
 }


 System.out.println("Best Buy Price : "+ currentBestBuyPrice + " on day "+ lowindex);
 System.out.println("Best Sell Price : "+ currentBestSellPrice+ " on day "+ highindex );

Balch

Answer 15

F# solution for those who interested in functional take on this. I wouldn't say though it's that much different.

let start, _, profit = 
    [55.39; 109.23; 48.29; 81.59; 81.58; 105.53; 94.45; 12.24 ]
    |> Seq.fold (fun (start,newStart,profit) i -> 
                    let start = defaultArg start i
                    let newStart = defaultArg newStart i
                    let newProfit = i - newStart
                    if profit < newProfit 
                    then  Some newStart, Some newStart,newProfit
                    else if start > i 
                    then Some start, Some i, profit 
                    else Some start,Some newStart,profit) (None,None, 0.0)
printf "Best buy: %f; Best sell: %f" start.Value (start.Value + profit)

Output:

Best buy: 48.290000; Best sell: 105.530000

Theomania

Answer 16

Here is my solution in Ruby:

values = [55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24]

max_diff = 0
diff = 0
min = values[0]
max = 0

values.each_with_index do |value, index = 1|
  # get an array of the previous values before the current one
  lag_values = values[0..index]

  # get the minimum of those previous values
  min_lag_value = lag_values.min

  # difference between current value and minimum of previous ones
  diff = values[index].to_i - min_lag_value.to_i

  # if current difference is > previous max difference, then set new values for min, max_diff, and max
  if diff > max_diff
    max_diff = diff
    min = min_lag_value
    max = values[index]
  end
end

min # => 48.29
max # => 105.3
max_diff # => 57

Cheers

Vitalize

Answer 17

I got 100% for the same, here you go.

public int solution(int[] A) {
      if (A == null || A.length<=1){
            return 0;
        }
        int minValue = Math.min(A[0], A[1]);
        int profit = A[1] - A[0];
        for (int i = 2; i < A.length; i++) {
          minValue = Math.min(minValue, A[i]);
          profit = Math.max(A[i] - minValue,profit);
        }

        return profit > 0 ? profit : 0;
}

Jeannettejeannie

Answer 18

The way I thought about this was, for every index i what would be the ideal index be for selling this stock? This is of course, the index of the maximum value after i. This reduces our problem to finding the maximum element after index i for each i in [1 ... n] If we could do that in O(n) time, then we could find the best choice amongst those and report it.

A way to do this is to start traversing from the end of the array, maintaining two variables, one to save the largest element we have encountered so far max_till_now, and one to save the maximum profit we could get till now, profit. This is just so that we can do this in one pass. We could also use extra space and for each element i, store the index of the largest element in the range [i + 1 ... n] for it and then find the maximum profit.

Here's my python code:

def buyLowSellHigh(L):
    length = len(L)
    profit = 0
    max_till_now = L[length - 1]
    for i in xrange(length - 2, -1, -1):
        if L[i] > max_till_now: max_till_now = L[i]
        else:
            if max_till_now - L[i] > profit: profit = max_till_now - L[i]
    return profit

Ladyfinger

Answer 19

Another Ruby solution:

# Here's some examples. Please feel free to give your new test.
values = [55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24]
# values = [5, 6, 4, 7, 9, 8, 8]
# values = [5, 10, 4, 6, 7]
# values = [5, 10, 4, 6, 12]
# values = [1, 2, 3, 4, 5]



# Initialize parameters.
min = values[0]
best_buy_time = values[0]
best_sell_time = values[0]
max_profit = 0



# This solution is based on comparing previous k elements and k+1 one.
# The runtime is O(n) and it only use O(1) auxiliary storage.
values.each_with_index do |value, index = 1|

  # Check value in this turn.
  puts value

  # Check current value is bigger than min or not.
  # If not, we find the new min.
  if value <= min
    min = value

  # If current value is bigger than min and
  # (value - min) is bigger than previous max_profit,
  # set new best_buy_time, best_sell_time & max_profit.
  else
    if value - min >= max_profit
      best_buy_time = min
      best_sell_time = value
      max_profit = value - min
    end

  end

end



# Let's see about the result.
puts "\nbest_buy_time: ", best_buy_time, "\nbest_sell_time: ", best_sell_time, "\nmax_profit: ", max_profit

Unwilled

Answer 20

what about this?

min = 100000000
max = 0

for elem in inp:
    if elem < min:
       min = elem
    tempMax = elem-min
    if tempMax > max:
        max = tempMax

print(max)

Deist

Answer 21

Solution in javascript

var stockArr = [13931, 9889, 987, 4, 89, 100];

function getBestTime(sortedArr) {
  var min = 0;
  var buyIndx = 0;
  var saleIndx = 0;
  var maxDiff = 0;
  for (var i = 0; i < stockArr.length; i++) {
    if (stockArr[i] < stockArr[min]) {
      min = i;
    }
    var diff = stockArr[i] - stockArr[min];
    if (diff > maxDiff) {
      buy = min;
      sale = i;
      maxDiff = diff;
    }
  }
  return {
    buy:buy+1,
    sale:sale+1,
    diff:maxDiff
  }
}

console.log(getBestTime(stockArr));

Ponytail

Answer 22

Heres a javascript solution..

function getMax(arr){
        //we need more than at least 3 ints to be able to do this
        if(arr.length <= 1) return arr;
        // get the minimum price we can sell at to make a profit
        var min = arr[0];
        //get the first potential maximum profit
        var max = arr[1] - arr[0];

        //while looping through we must get a potential value, 
       //we can then compare that using the math.max using the maximum
      //and the potential prices that we have seen. Once the loop runs the ouput here should be 6!
        for(var i = 1; i < arr.length; ++i){
            var current = arr[i];
            var potential = current - min;

            max = Math.max(max, potential);
            min = Math.min(min, current);
        }

        return max;
    }

    console.log(getMax([10, 7, 5, 8, 11, 9]));

Runtime on this is O(n)

Daphne

Answer 23

Solution in scala :

Example : [ 7, 2, 5, 6, 1, 3, 6, 4 ]

Keep a pointer to the last minimum stock price(lastStockPrice) and compare it to the current stock price. When you reach a point where the current stock price < last minimun stock price, you update the lastStockPrice.

While looping through the array, keep a track of the max difference (profit) between the currentPrice and the lastStockPrice as the profit can change when you update the lastStockPrice.

The below scala code works in O(n) time and takes a constant amount of space.

object Solution {
    def maxProfit(prices: Array[Int]): Int = {
        var lastStockPrice = Int.MaxValue
        var maxProfit = 0
        for(currentPrice <- prices){
            if(currentPrice < lastStockPrice){
                lastStockPrice = currentPrice;
            }else if(currentPrice - lastStockPrice > maxProfit){
                maxProfit = currentPrice - lastStockPrice;
            }
        }
        maxProfit
    }
}

Disadvantage

Answer 24

The logic to solve this problem is same as "max subarray problem" using Kadane's Algorithm. Since no body has mentioned this so far, I thought it's a good thing for everybody to know.

All the straight forward solution should work, but if the interviewer twists the question slightly by giving the difference array of prices, Ex: for {1, 7, 4, 11}, if he gives {0, 6, -3, 7}, you might end up being confused.

Here, the logic is to calculate the difference (maxCur += prices[i] - prices[i-1]) of the original array, and find a contiguous subarray giving maximum profit. If the difference falls below 0, reset it to zero.

class Solution:
def maxProfit(self, prices: List[int]) -> int:
    
    _currmax = 0
    _globalMax = 0
    
    for i in range(1,len(prices)):
        
        _currmax = max(_currmax+(prices[i]-prices[i-1]),0)
        _globalMax = max(_globalMax,_currmax)
        
    return _globalMax

Welldefined