Ruby - Given an array of nested arrays, how to find the max only comparing the last value of each nested array?

Question

Beginner trying to create a simple stock picker program. So far my program takes a flat array of integers representing stock prices (indices are days) and returns an array of nested arrays. Each nested array has three values [each consecutive buy day index, best sell day index, profit]. Like so:

stock_prices = [17, 2, 20, 6, 9, 15, 8, 1, 15, 15]
best_days = [[ 0,  2,  3], [ 1,  2, 18], [ 2,  5, -5], 
             [ 3,  5,  9], [ 4,  5,  6], [ 5,  8,  0], 
             [ 6,  8,  7], [ 7,  8, 14], [ 8,  9,  0]]

I would like to find the max profit day, then return an array that contains the index values of the buy and sell days of that day. In this case it would be:

absolute_best = [1, 2]

How do I iterate through an array of nested arrays but only compare the final value of each nested array?

Answer 1

We can speed up the determination of the desired result as follows. Let me explain the procedure with an example that is slightly modified from the one given in the question. (I changed arr[6] from 8 to 10.)

arr  = [17, 2, 20, 6, 9, 15, 10, 1, 15, 15]
days = [ 0, 1,  2, 3, 4,  5,  6, 7,  8,  9]

We first consider selling on the last day, day 9. Should we do so, the best buy date is

days.pop
days
  #=>  [ 0, 1,  2, 3, 4,  5,  6, 7,  8]
days.min_by { |d| arr[d] }
  #=> 7 (note arr[7] => 1)

The best pair found so far is given by

[7, 9, 14]

or, expressed as a hash,

{ buy_day: 7, sell_day: 9, net: 14}

We may now eliminate all days d strictly between 7 and 9 for which

arr[d] <= arr[9]

which is here day 8. We are now left with

days = [ 0, 1,  2, 3, 4,  5,  6, 7]

We now consider selling on new last day, day 7. The best we can do is given by

{ buy_day: 1, sell_day: 7, net: -1 }

As -1 < 14, this solution is seen to be sub-optimal. We may now eliminate all days d strictly between 1 and 7 for which

arr[d] <= arr[7]

of which there are none. We next consider

days = [ 0, 1,  2, 3, 4,  5,  6]

and selling on day 6. As the previous best buy date was 1 this obviously will be the best buy date for all sell dates between 2 and 6.

We see that the best solution when selling on day 6 is

{ buy_day: 1, sell_day: 6, net: 8 }

which again is sub-optimal. We may now eliminate all days d strictly between 1 and 6 for which

arr[d] <= arr[6]

of which there are two, days 3 and 4. We therefore next consider

days = [0, 1, 2, 5]

obtaining

{ buy_day: 2, sell_day: 5, net: 13 }

which is found to be sub-optimal (13 < 14). Day 2 cannot be eliminate (since arr[2] > arr[5]) so the new problem becomes

days = [0, 1, 2]

The solution here is

{ buy_day: 0, sell_day: 2, net: 18 }

which is found to be the new optimum. Lastly,

days = [0, 1]

is considered. As

days.pop
days = [0]
days.min_by { |d| arr[d] }
  #=> 0

the solution for selling on day 1 is

{ buy_day: 0, sell_day: 1, net: -15 }

which is sub-optimal. The next problem is

days = [0]

Since the array now has only one element we are finished, with the optimal solution being

{ buy_day: 0, sell_day: 2, net: 18 }

---

We can write a method to implement the above approach to computing an optimal buy-sell pair as follows. Note that I have included a puts statement to illustrate the calculations being made. That statement should of course be removed.

def doit(arr,
         days = arr.size.times.to_a,
         sell_day = days.pop,
         buy_day = days.min_by { |d| arr[d] },
         best = { buy_day: nil, sell_day: nil, net: -Float::INFINITY })
  puts "days=#{days}, sell_day=#{sell_day}, buy_day=#{buy_day}, best=#{best}"
  return best if days.size == 1
  sell_price = arr[sell_day]
  candidate = sell_price - arr[buy_day]
  best = { buy_day: buy_day, sell_day: sell_day, net: candidate } if
    candidate > best[:net]
  days.reject! { |d| d > buy_day && arr[d] <= sell_price }
  sell_day = days.pop
  buy_day = days.min_by { |d| arr[d] } if sell_day <= buy_day
  doit(arr, days, sell_day, buy_day, best)
end

arr = [17, 2, 20, 6, 9, 15, 10, 1, 15, 15]

doit(arr)
days=[0, 1, 2, 3, 4, 5, 6, 7, 8], sell_day=9, buy_day=7,
  best={:buy_day=>nil, :sell_day=>nil, :net=>-Infinity}
days=[0, 1, 2, 3, 4, 5, 6],       sell_day=7, buy_day=1,
  best={:buy_day=>7, :sell_day=>9, :net=>14}
days=[0, 1, 2, 3, 4, 5],          sell_day=6, buy_day=1,
  best={:buy_day=>7, :sell_day=>9, :net=>14}
days=[0, 1, 2],                   sell_day=5, buy_day=1,
  best={:buy_day=>7, :sell_day=>9, :net=>14}
days=[0, 1],                      sell_day=2, buy_day=1,
  best={:buy_day=>7, :sell_day=>9, :net=>14}
days=[0],                         sell_day=1, buy_day=0,
  best={:buy_day=>1, :sell_day=>2, :net=>18}

  #=> {:buy_day=>1, :sell_day=>2, :net=>18}

Answer 2

To find the largest array element by a condition (here: the value of its 3rd element) you can use max_by in various ways.

Using array decomposition to extract the 3rd element:

best_days.max_by { |a, b, c| c }

# or

best_days.max_by { |_, _, c| c }

# or

best_days.max_by { |*, c| c }

Using the array as is and retrieve its last value:

best_days.max_by { |ary| ary.last }

# or

best_days.max_by(&:last)

All of the above return [1, 2, 18].

In addition to max_by there's also sort_by which can be used to sort the array by profit.