Need help manipulating an array in ruby

Question

I'm trying to find the the best time to buy and sell these "stocks". For instance in array "f" buying on 3 and selling at 15 would = maximum_profit. I'm struggling to figure this out, starting to feel slightly dumb. I need to iterate through the array and find the best combo but once I pass a "day" I cant sell it on a day before that, only after.

 a = [1, 2, 3, 4, 5, 6, 7, 8, 9] 
 b = [9, 8, 7, 6, 5, 4, 3, 2, 1] 
 c = [3, 4, 2, 6, 7, 4, 9, 8, 5] 
 d = [8, 6, 9, 2, 7, 4, 1, 5 ,1] 
 e = [10, 11, 2, 9, 4, 3, 5, 6] 
 f = [17, 3, 6, 9, 15, 8, 6, 1, 10] 

 def stock_picker(array)
   min = array.min
   min_price= array.index(min)
   max = array.max
   max_price = array.index(max)

 end

 stock_picker(a)

Answer 1

My answer is an exercise to find an efficient way of solving the problem.

Code

def buy_sell(prices)
  n = prices.size
  imax = (1..n-1).max_by { |i| prices[i] }
  imin = (0..imax-1).min_by { |i| prices[i] }
  return [imin, imax] if imax >= n-2
  imin_next, imax_next = buy_sell(prices[imax+1..-1]).map { |i| i + imax }
  prices[imin]-prices[imax] >= prices[imin_next]-prices[imax_next] ? [imin, imax] :
    [imin, imax]
end

This is for prices.size >= 2.

Example

prices = [17, 3, 6, 9, 15, 8, 6, 1, 10]
buy_sell(prices)
  #=> [1, 4]

This means that the greatest profit can be made by buying at prices[1] #=> 3 on day (offset of prices) 1 and selling at prices[4] #=> 15 on day 4, for a profit of 12.

Explanation

Consider the following array of daily prices.

prices = [17, 3, 6, 9, 15]

17 is the price on day (offset) 0, 3 is the price on day 1, and so on.

We might first determine the index i > 0 of prices for which prices[i] is greatest.

n = prices.size
  #=> 5
imax = (1..n-1).max_by { |i| prices[i] }
  #=> 4

Since imax #=> 4 we see that prices' largest value after the first day is on its last day, where prices[imax] #=> 15. That tells us that regardless of when we will buy, we should sell on the last day (proved easily by contradiction). It therefore remains to compute:

imin = (0..imax-1).min_by { |i| prices[i] }
  #=> 1

We therefore should buy on day 1, at prices[1] #=> 3 and sell on day 4 at 15, giving us a tidy profit of 12.

Of course, the largest price after the first day is not necessarily on the last day. Now suppose:

 prices = [17, 3, 6, 9, 15, 8, 6, 1, 10]

which is the OP's example. The calculation of the maximum price after the first day is now:

n = prices.size
  #=> 9
imax = (1..n-1).max_by { |i| prices[i] }
  #=> 4

15, on day 4 is still the highest price and we already know that before day 4, day 1 has the lowest price. This allows us to conclude the following: we should either buy on day 1 and sell on day 4, or we should buy after day 4 (and sell after that). Again, this is easily proved by contradiction, as selling anytime after day 4 will give us a sell price of at most 15, so we cannot have a larger profit than 12 by buying before day 4. The remaining problem is the array

 prices = [8, 6, 1, 10]

where 8 is the price on day 5, and so on.

Since the largest sell price in this array is at the end, we know that the optimum is to buy at 1 on day 7 (offset 2 of the new prices) and sell on day 8 (offset 3), yielding a profit of 9. Since 9 < 12 we see that the highest profit is what we calculated initially.

Had prices here been [1, 10, 8, 6] we would have computed the same profit of 9, but then had to consider prices being the array [8, 6]. Had prices here been [8, 1, 10, 6] we would have computed the same profit of 9, but then had to consider prices being the array [6], which we could disregard since it only contains single price.

This algorithm lends itself to a recursive implementation.

Efficiency

If there are m subarrays to consider, the time complexity is O(mn), compared to O(n²) for a straightforward comparison of all pairs [prices[i], prices[j]], i < j.

I have performed a benchmark to compare this approach with a simplified version of that used by @tadman, which enumerates all ordered pairs. The results are as follows.

def cary_buy_sell(prices)
  n = prices.size
  imax = (1..n-1).max_by { |i| prices[i] }
  imin = (0..imax-1).min_by { |i| prices[i] }
  return [imin, imax] if imax >= n-2
  imin_next, imax_next = cary_buy_sell(prices[imax+1..-1]).map { |i| i + imax }
  prices[imin]-prices[imax] >= prices[imin_next]-prices[imax_next] ? [imin, imax] :
    [imin, imax]
end

def tadman_buy_sell(prices)
  prices.combination(2).max_by { |x,y| y-x }
end

require 'fruity'

m = 20
[10, 20, 100, 1000].each do |n|
  puts "\nn = #{n}, m = #{m}"
  prices = m.times.map { n.times.to_a.shuffle }
  compare do
    tadman { prices.each { |row| tadman_buy_sell(row) } }
    cary   { prices.each { |row| cary_buy_sell(row) } }
  end
end

reports the following.

n = 10, m = 20
Running each test 16 times. Test will take about 1 second.
cary is faster than tadman by 1.9x ± 0.1

n = 20, m = 20
Running each test 8 times. Test will take about 1 second.
cary is faster than tadman by 4x ± 0.1

n = 100, m = 20
Running each test once. Test will take about 1 second.
cary is faster than tadman by 22x ± 1.0

n = 1000, m = 20
Running each test once. Test will take about 28 seconds.
cary is faster than tadman by 262x ± 10.0

Out of curiosity I computed the average number of recursions required for each value of n tested. The results are as follows.

           average number of
    n     recursions required
---------------------------
     10          2.40
     20          2.55
    100          4.50
  1,000          6.65
 10,000          8.55
 50,000          9.85
100,000         11.60
500,000         13.40

When n equals 100, for example, on average, a sequence of 4.50 recursive calculations were required (i.e., each determining the maximum value of a subarray of prices and then determining the minimum value preceding the maximum). Not unexpectedly, that number increases slowly as n is increased.

Answer 2

Here's a more Ruby way to solve the problem. The key here is to leverage tools like combination to do a lot of the heavy lifting for you, then transform that data step by step into the desired end result:

def max_profit(prices)
  best = prices.combination(2).map do |buy, sell|
    [ buy, sell, sell - buy ]
  end.max_by do |buy, sell, profit|
    profit
  end

  if (best[2] <= 0)
    {
      profit: 0
    }
  else
    {
      buy: {
        at: best[0],
        on: prices.index(best[0])
      },
      sell: {
        at: best[1],
        on: prices.index(best[1])
      },
      profit: best[2]
    }
  end
end

stocks = [
  [1, 2, 3, 4, 5, 6, 7, 8, 9],
  [9, 8, 7, 6, 5, 4, 3, 2, 1],
  [3, 4, 2, 6, 7, 4, 9, 8, 5],
  [8, 6, 9, 2, 7, 4, 1, 5 ,1],
  [10, 11, 2, 9, 4, 3, 5, 6],
  [17, 3, 6, 9, 15, 8, 6, 1, 10]
] 

stocks.each do |prices|
  p max_profit(prices)
end

This gives you results like this:

{:buy=>{:at=>1, :on=>0}, :sell=>{:at=>9, :on=>8}, :profit=>8}
{:profit=>0}
{:buy=>{:at=>2, :on=>2}, :sell=>{:at=>9, :on=>6}, :profit=>7}
{:buy=>{:at=>2, :on=>3}, :sell=>{:at=>7, :on=>4}, :profit=>5}
{:buy=>{:at=>2, :on=>2}, :sell=>{:at=>9, :on=>3}, :profit=>7}
{:buy=>{:at=>3, :on=>1}, :sell=>{:at=>15, :on=>4}, :profit=>12}

One of the important properties about combination is it preserves the order of the elements so this automatically excludes trades that would be impossible by happening in the wrong order.