get_max_profit.rb

# prices = [11, 7, 5, 8, 10, 9]
# => 5
# ALGO 1: BRUTE FORCE
# for each map to profit, find biggest number
#   11 => [-4, -6, -3, -1, -2]
#   7  => [-2, 1, 3, 2]
#   5  => [3, 5, 4]
#   8  => [2, 1]
#   10 => [-1]
#
# O(n!) (actually n-1!) because iterating the array over and over subtracting 1 length each time
# 
# PRO: Simple algorithm
# CON: Extremely slow on large input

# ALGO 2
# map to difference between elements
# => [-4, -2, 3, 2, -1]
# looking for sum of largest postive integers
#   transformation O(n)
# map to array of arrays
# => [[3, 2]]
# BRUTE FORCE find max sum value
#
# O(n): first iteration n time (n iterations)
#       summing of array of arrays worst case is an array of an n length array (n iterations)
# 
# PRO: Time & Memory efficient
# CON: harder to read algorithm, additional complexity (kind of comes with the turf)

# X ALGO 3
# reversed problem (reversing array) and looking for largest drop
# -- Doesnt seem to help problem

# ALGO 4
# ???

def get_max_profit(prices)
  profits(prices).reduce([[]]) do |acc, profit|
    if profit < 0 && acc.last.size != 0
      acc << []
    elsif profit >= 0
      acc.last << profit
    end
    acc
  end.map(&:sum).max
end

def profits(prices)
  prices[1..-1].each_with_index.map do |price, i|
    price - prices[i]
  end
end