Help regarding a problem

[Geetha Reddy]

Hi All, I have the following problem. can you help me in solving this.

Suppose we could access yesterday's stock prices as an array where:

 

- The indices are the time in minutes past trade opening time, which was 9:30 am local time

- The values are the price in dollars of Apple stock at that time

 

So if the stock cost $500 at 10:30am, stock_prices_yesterday[60] = 500

 

Write an efficient function that takes stock_prices_yesterday and returns the best profit I could have made 1 purchase and 1 sale of 1 Apple stock yesterday.

 

Below is a solution that uses brute force algorithm. Big 0(n2). Can you write an improved solution at Big 0(n2) or even better Big 0(n)

 

def get_max_profit(stock_prices_yesterday)

 

  max_profit = 0

 

    # go through every time

    for outer_time in (0...stock_prices_yesterday.length)

 

        # for every time, go through every OTHER time

        for inner_time in (0...stock_prices_yesterday.length)

 

            # for each pair, find the earlier and later times

            earlier_time = [outer_time, inner_time].min

            later_time   = [outer_time, inner_time].max

 

            # and use those to find the earlier and later prices

            erlier_price = stock_prices_yesterday[earlier_time]

            later_price  = stock_prices_yesterday[later_time]

 

            # see what our profit would be if we bought at the

            # earlier price and sold at the later price

            potential_profit = later_price - earlier_price

 

            # update max_profit if we can do better

            max_profit = [max_profit, potential_profit].max

        end

    end

    return max_profit

end