Max Difference
Design an algorithm that determines the maximum profit that could have been made by buying and then selling a single share over a given day range, subject to the constraint that the buy and the sell have to take place at the start of the day.
Example
compute_max_diff([1,2,3,4,5,6,7,8,9]) # => 8
Algorithm
- Keep a running counter of the max_diff_so_far
- Keep a running counter of the min_so_far
- Run through the entire array
- Once all elements are exhaused the max diff is available in max_diff_so_far
Code
def compute_max_diff(elements)
max_diff_so_far = 0
min_so_far = 999
elements.each do |e|
min_so_far = [e, min_so_far].min
max_diff_so_far = [max_diff_so_far, e - min_so_far].max
end
max_diff_so_far
end
Test cases
compute_max_diff([1,2,3,4,5,6,7,8,9]) # => 8
compute_max_diff([9,1]) # => 0
compute_max_diff([5,15,3]) # => 10
compute_max_diff([5,15,3,20]) # => 17
Time complexity
- O(n), since we are looping over the array only once.