Question

Can someone help me with a function for this.

Also, what BIG O notation would the function be?

stock prices change from day to day.

we might have: {4,-1,-2,3,5,-7,1,0,0,-2,4}.

Which meant if we bought the stock after the second day, and held it for 3 days, the price would go down by 2, then up by 3, and then up by 5. If we sold it then, we would have made $6.

Design an O(N²) or better (it can actually be done in O(N) time) algorithm to find the days to buy and sell the stock that makes you the most profit (as well as the profit made). It is possible that every combination of days will lose you money, in which case you should not buy the stock at all and have a profit of $0.

Answer 1

answer:

If we are allowed to buy and sell once we use the following algorithm.

let us first define the algorithm in general sentences.

1) First we need to find the point where the value is least and take it as starting index.

2) Second, we need to find the point where the value is maxed and take it as ending index.

Algorithm:

step 1: Start

step 2: Decalre price array and n(length)

step 3: Read the value of the stock_price change and assign to price_arrayy and initialize n = length of the array and i=0,j=0

step 4: Initialize num_of_ways_buysell=0 and define sell_date and buy_date array

step 5: if n==1: return the value should be greater than one

step 6: while i should be less than n-1:

//find local minima which are our starting index:

while i< n-1 and stock_price[i+1] should be less than or equal to stock_price[i]

increment i by 1

if i == n-1

// this condition is true if i value is reached least on end day

break the loop

buy_date[j] = i

increment i by 1

// find local maxima which are ending index.

while (( i should be less than n ) and stock_price[i] should be greater than or equal to price[i-1])

increment i by 1

sell_date[j] = i-1

num_of_ways_buyssell increment by 1

increment j by 1

step 7: if num_of_ways_buyssell is equal to zero then

display then there is no day to buy the stock which gives profit

else:

for i=0 to j-1

display "Buy day "buy_date[i] "Sell day"sell_date[i]

step 8: stop

Yes, It is possible that every combination of days will lose you money, in which case you should not buy the stock at all and have a profit of $0. This condition is achieved in the algorithm when num_of_ways_buyssell.

The overall time complexity is O(n)

Thank you:)