Hieu Nguyen

# Leetcode - Best time to buy and sell stock

Nov 29 2017

Recently, our chat group in RubyVN starts a channel called `#algorithm` for discussing competitive programming. This week, this is one of the three problems that we will discuss:

Level: easy

# Solution

## Naive approach

Loop through all possible combinations to find the combination that has max profit:

``````def max_profit(prices)
size = prices.size
max = 0

prices.each_with_index do |price, index|
prices[(index+1)..(size-1)].each do |price_2|
max = [max, price_2 - price_1].max
end
end

max
end
``````

This solution needs to one nested loop to get all combinations, so its time complexity is O(n^2), which is not so good. It will cause Time Limit Exceed on leetcode.

## First optimization

With observation, we can figure out the equation for max profit of a position i:

``````max_profit[i] = max[i, size - 1] - min[0, i]
``````

We can cache `max[i, size - 1]` and `min[0, i]` to two arrays, then calculate the max profit based on those:

``````def max_profit(prices)
min = 0
min_array = prices.map do |price|
min = [min, price].min
end

max = 0
max_array = prices.reverse.map do |price|
max = [max, price].max
end

(0..(prices.size - 1)).inject(0) do |profit, index|
[profit, max_array[index] - min_array[index]].max
end
end
``````

This solution needs 3 loops through the array, so it’s 3xn, or O(n) complexity. It’s also need 2 more arrays to cache the value of `max[i, size-1]` and `min[0, i]`.

## Final optimization

With further observation, we can see that we don’t need two arrays to cache the value. Instead, we can calculate them on the fly:

``````def max_profit(prices)
return 0 if prices.empty?

min = prices.first
profit = 0

prices.each do |price|
min = [price, min].min
profit = [price - min, profit].max
end

profit
end
``````

This solution requires only 2 temp variables and only one loop, so it’s a little bit better than the previous optimization.