Skip to content

Instantly share code, notes, and snippets.

@mgwidmann
Created November 28, 2017 05:44
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save mgwidmann/823b29e76c0a3da722b0bc7a01f6f0a7 to your computer and use it in GitHub Desktop.
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment