stock trader, O(n) time complexity

best-stock-trade-fast.clj

;; for context:
;; http://stackoverflow.com/questions/7086464/maximum-single-sell-profit/


(def PRICES [5 10 4 6 7 1 7])

(defn day [[ndx low profit sell-ndx] price]
  (let [nprofit (max profit (- price (or low price)))
        nlow (if low (min low price) price)
        nsell-ndx (if (> nprofit profit) ndx sell-ndx)]
    [(inc ndx) nlow nprofit nsell-ndx]))

(comment 
  (reduce day [0 nil 0 0] PRICES)
)

;; Alan's version, returns pertinent data
(defn best-trade-dynamic [prices]
  (loop [i 1, prices (next prices),
         buy 0, sell 0, profit 0,
         lowi 0, low (first prices)]
    (if-let [[x & more] prices]
      (let [profit' (- x low)
            [low lowi] (if (< x low)
                         [x i]
                         [low lowi])]
        (if (> profit' profit)
          (recur (inc i) (next prices) lowi    i profit' lowi low)
          (recur (inc i) (next prices)  buy sell profit  lowi low)))
      {:buy buy, :sell sell, :profit profit})))

;; Alan's version, returns buy price and profit
(defn best-trade-dynamic-easy [prices]
  (second 
   (reduce (fn [[low profit] x]
             [(min low x), (max profit (- x low))])
           [(first prices) 0]
           (next prices))))