Interview Questions

Stock maximum profit

The question is as follows:
## Algorithm

We'll solve the challenge the following way:
*n*).
## Example

Here is an example of the values that are set through each iteration of the stock prices.
input = [45, 24, 35, 31, 40, 38, 11]
buy_price = 0
sell_price = 0
max_profit = -1
At i = 0
buy_price = 45
sell_price = 24
max_profit = -1
At i = 1
buy_price = 24
sell_price = 35
max_profit = 11
At i = 2
buy_price = 24
sell_price = 31
max_profit = 11
At i = 3
buy_price = 24
sell_price = 40
max_profit = 16
At i = 4
buy_price = 24
sell_price = 38
max_profit = 16
At i = 5
buy_price = 24
sell_price = 11
max_profit = 16
Loop is done
max_profit = 16
## Code

## Sources

https://www.glassdoor.com/Interview/You-have-all-of-the-prices-for-a-given-stock-for-the-next-year-You-can-buy...

You will be given a list of stock prices for a given day and your goal is to return the maximum profit that could have been made by buying a stock at the given price and then selling the stock later on. For example if the input is: [45, 24, 35, 31, 40, 38, 11] then your program should return 16 because if you bought the stock at $24 and sold it at $40, a profit of $16 was made and this is the largest profit that could be made. If no profit could have been made, return -1.

(1) Iterate through each number in the list.
(2) At the ith index, get the i+1 index price and check if it is larger than the ith index price.
(3) If so, set buy_price = i and sell_price = i+1. Then calculate the profit: sell_price - buy_price.
(4) If a stock price is found that is cheaper than the current buy_price, set this to be the new buying price and continue from step 2.
(5) Otherwise, continue changing only the sell_price and keep buy_price set.

This algorithm runs in linear time, making only one pass through the array, so the running time in the worst case is O(function StockPicker(arr) { var max_profit = -1; var buy_price = 0; var sell_price = 0; // this allows our loop to keep iterating the buying // price until a cheap stock price is found var change_buy_index = true; // loop through list of stock prices once for (var i = 0; i < arr.length-1; i++) { // selling price is the next element in list sell_price = arr[i+1]; // if we have not found a suitable cheap buying price yet // we set the buying price equal to the current element if (change_buy_index) { buy_price = arr[i]; } // if the selling price is less than the buying price // we know we cannot make a profit so we continue to the // next element in the list which will be the new buying price if (sell_price < buy_price) { change_buy_index = true; continue; } // if the selling price is greater than the buying price // we check to see if these two indices give us a better // profit then what we currently have else { var temp_profit = sell_price - buy_price; if (temp_profit > max_profit) { max_profit = temp_profit; } change_buy_index = false; } } return max_profit; } StockPicker([44, 30, 24, 32, 35, 30, 40, 38, 15]);

def StockPicker(arr): max_profit = -1 buy_price = 0 sell_price = 0 # this allows our loop to keep iterating the buying # price until a cheap stock price is found change_buy_index = True # loop through list of stock prices once for i in range(0, len(arr)-1): # selling price is the next element in list sell_price = arr[i+1] # if we have not found a suitable cheap buying price yet # we set the buying price equal to the current element if change_buy_index: buy_price = arr[i] # if the selling price is less than the buying price # we know we cannot make a profit so we continue to the # next element in the list which will be the new buying price if sell_price < buy_price: change_buy_index = True continue # if the selling price is greater than the buying price # we check to see if these two indices give us a better # profit then what we currently have else: temp_profit = sell_price - buy_price if temp_profit > max_profit: max_profit = temp_profit change_buy_index = False return max_profit print StockPicker([44, 30, 24, 32, 35, 30, 40, 38, 15])

mrdaniel
published this on 1/3/16 **|**

8

I am confused as to why the "continue" keyword is used here. It seems to me that the code would (and does) execute just fine without it?
Was there a specific reason it was left in there?
Thanks so much!

gabewr

commented on 05/28/16

1

The question is a bit misleading. It says "by buying a stock at the given price and then selling the stock later on". The buy price is not given. Would be much clearer to say "buy once and sell once".

romanov

commented on 08/13/17

1

I'd like to suggest that using array.reduce() is the most streamlined approach for such a problem:

function StockPicker(arr) { let trueMax = 0; arr.reduce(function(prev, item){ let max = Math.max(item - prev, 0); max > trueMax ? trueMax = max : null; if (max === 0) { return item; } else { return prev; } }); if (trueMax === 0) { return -1; } return trueMax; }

thedragon

commented on 07/16/16

1

Keep track of the lowest i've seen so far (lissf), compare current index to compute profit

function StockPicker(arr) { let lissf = arr[0] let profit = -1 for(let i = 1; i < arr.length; i++) { if(arr[i] > lissf) { profit = Math.max(profit, arr[i] - lissf) } else { lissf = arr[i] } } return profit }

nagolyhprum

commented on 12/21/18

1

def StockPicker(arr): bp=0 sp=0 mp=-1 for r in arr: if arr[arr.index(r)+1] > r: bp=r break sp=max(arr[_] for _ in range(arr.index(bp),len(arr))) if sp-bp > mp: return sp-bp else: return mp print(StockPicker([44, 30, 24, 32, 35, 30, 40, 38, 15]))

kumarvinod002

commented on 01/23/19

1

This is how I did it.
var profitArray is map of the agumented array.
It takes every value a turns it into the profit one would make if he bought the stocks that day and sold them on the most expensive day left.
profitArray.sort(function(a, b){return b-a})[0] simply returns the highest value of profit opportunities

function maxProfit(array) { var profitArray = array.map(function(currentValue, index) { return array.slice(index, array.length) .sort(function(a, b){return b-a})[0] - currentValue }) return profitArray.sort(function(a, b){return b-a})[0]; } console.log(maxProfit([45, 24, 35, 31, 40, 38, 11]));

niclaflamme

commented on 06/28/16

0

function stock(arr){ var buy = -1, sell =-1, profit = -1; var changeSellPrice = true; for(var i=0; i< arr.length; i++){ // assigning "buy" value inside the array because if array is empty, buy would be -1 if(buy===-1){ buy= arr[i]; } if(buy> arr[i]){ buy = arr[i]; changeSellPrice = true; } if(changeSellPrice || sell< arr[i+1] ){ sell = arr[i+1]; if(profit< (sell-buy)){ profit = sell - buy; changeSellPrice = false; } } } return profit; }

yzarina

commented on 03/20/18

0

function maxStock(arr){ if(arr[0] > arr[1]){ var redundant = arr.shift(); var newArr = arr; var maxPrice = Math.max.apply(null, newArr); var minPrice = Math.min.apply(null, newArr); if(newArr.indexOf(maxPrice) > newArr.indexOf(minPrice)){ var maxProfit = maxPrice - minPrice; } else { while(newArr.indexOf(minPrice) > newArr.indexOf(maxPrice)){ newArr.splice(newArr.indexOf(minPrice), 1); } var newMin = Math.min.apply(null, newArr); maxProfit = maxPrice - newMin; } } return maxProfit; }

bpaksoy

commented on 12/09/16

0

def stockExchange(stockPrices): buy = stockPrices[0] sell = 0 profit = -1 for n in range(0,len(stockPrices)-1): x = stockPrices[n] if x < buy: buy = x sell = 0 elif x > sell: sell = x profit = sell - buy return profit

bterryjack

commented on 09/29/17

0

I tried this way...

function stock(array){ var min= array[0]; var max= -1; var profit= 0; for(var idx in array){ if(array[idx]<min){ min= array[idx]; max= -1; } if(array[idx]>max){ max= array[idx]; if(max-min>profit){ profit= max-min; } } } return profit; } console.log(stock([44, 30, 24, 32, 35, 30, 40, 38, 15]));

JibranGarcia

commented on 06/05/16

-5

My version, but I am not quite convinced by this problem.

var maxArray = arr; maxArray.shift(); var minArray = arr; minArray.pop(); var min = Math.min.apply(null, minArray); var max = Math.max.apply(null, maxArray); return max-min;

natseg

commented on 07/01/16

Log in to submit a comment.