mgwidmann · November 28, 2017 05:44 · Nov 28, 2017
diff --git a/get_max_profit.rb b/get_max_profit.rb
@@ -0,0 +1,53 @@
+# 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