# Stock Market Problem

Completed an interview prep problem today. For these interview prep questions I attempt to solve the challenge then I re-solve following the outlined solution, in Ruby of course.

Problem: Stock Market Problem
Given array of elements representing stock prices over a day. Permitted to buy and sell 1 share of a stock. Design algorithm to find the best times to buy and sell.
* Best time = most profit
* Profit = buying price less than selling price
* You must buy before you sell
* Find i (buy) and j (sell) that maximizes Aj — Ai, where i < j.
* O(n^2) — Find all possible permutations and then determine the maximum profit.
* Solve in O(n)

Small note problems like these are solving to the Big(O)n by using a greedy algorithm. (Iterating through subset performing calculation and updating the optimal solution if it changes)

stocks = [3, 6, 10, 2, 66, 43, 1, 23]

Create a method-> def get_max_profit2(price_list)
set min price to first value in array-> min_price = price_list[0]
set max prof to second value in array minus the first value in array -> max_profit = price_list[1] — price_list[0]
Captures best sell time (index) -> sell_time = 0
Iterate through my array with the each_with_index method. (array.map.with_index also works here)
x = the current value and i = the current index ->
price_list.each_with_index do |x, i|
Because I initialized my min and max values already I can skip to the next index. This is a great trick to remember for the future. (if i < 2 then next end) real solid.->
if i == 0 then next end
I need to track the current price (or “value”) so that I can calculate my potential_profit ->
current_price = x
Using current value and initial min price I can calculate potential profit.-> potential_profit = current_price — min_price
Conditional statement testing my max profit vs potential profit
if max_profit < potential_profit
Redundant comparison done and assignment takes place here utilizing the max array (enum) method (returns obj with maximum value).
max_profit = [max_profit, potential_profit].max
This assignment is the entire reasoning behind my if condition. If my max profit changes then I need to store my sell time store index value->
sell_time = i
Closes if
end
Assign the min price to the lowest available stock price for that day min_price = [current_price, min_price].min
Closes iterator
end
Time to calculate the best buy time (index), lowest price before highest sell value. Using the calculated highest possible sell time (index) as an argument for the take array method ( returns a new array with the first N elements from the array). The next step is to find the smallest value (or price) from this returned array, because this is my buy value. The min array (enum) method will provide this value. Next use the index array method (return first index with matching value) to find the actually time (or index) of purchase.