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:
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.
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
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.