max_profit.clj

(defn profits
  "Takes a sequence of prices representing prices on consecutive days and returns a sequence of tuples containing
  possible profitable transactions resulting from buying and selling on those days. The first member of the tuple
  is a vector containing the 0 based day of purchase and sale. The second member is the profit from the transaction.
  E.g. an input of [1 7 1 5 4 20] will return
  ([[0 1] 6] [[0 3] 4] [[0 4] 3] [[0 5] 19] [[1 5] 13] [[2 3] 4] [[2 4] 3] [[2 5] 19] [[3 5] 15] [[4 5] 16])"
  [prices]
  (apply
    concat
    (keep-indexed
      (fn [buy-index buy-price]
        (keep-indexed
          (fn [sell-index sell-price]
            (let [profit (- sell-price buy-price)]
              (when (> profit 0)
                [[buy-index (+ sell-index buy-index)] profit])))
          (subvec prices buy-index)))
      prices)))

(defn overlapping?
  "Takes two profit tuples and determines if they overlap."
  [[[_ x-end]] [[y-start y-end]]]
  (or (<= y-start x-end)
      (<= y-end x-end)))

(defn non-overlapping-permutations
  "Takes a sequence of profit tuples and returns a sequence representing all permutations of non overlapping groups of size
  <= k. E.g. an input of:
  k = 2, ([[0 1] 6] [[0 3] 4] [[0 4] 3] [[0 5] 19] [[1 5] 13] [[2 3] 4] [[2 4] 3] [[2 5] 19] [[3 5] 15] [[4 5] 16])
  returns:
  [[[[0 1] 6] [[2 3] 4]] [[[0 1] 6] [[2 4] 3]] [[[0 1] 6] [[2 5] 19]] [[[0 1] 6] [[3 5] 15]] [[[0 1] 6] [[4 5] 16]]]"
  [k [profit & rst]]
  (->> (reduce
         (fn [[a k-profits] next-profit]
           (if (= (count k-profits) k)
             (if-not (overlapping? profit next-profit)
               [(conj a k-profits) [profit next-profit]]
               [(conj a k-profits) [profit]])
             (if-not (overlapping? (last k-profits) next-profit)
               [a (conj k-profits next-profit)]
               [a k-profits])))
         [[] [profit]]
         rst)
       (apply conj)))

(defn maximum-profits
  "Takes 'k', the maximum number of transactions, and a sequence of prices representing the price on a zero indexed day.
  Returns the maximum profit achievable in up to k buy/sell transactions. First calculate all possible profitable
  transactions then find all permutations of k sequential, non overlapping transactions.
  E.g. with k = 2 and prices = [1 7 1 5 4 20] we have:
  ([[[[0 1] 6] [[2 3] 4]] [[[0 1] 6] [[2 4] 3]] [[[0 1] 6] [[2 5] 19]] [[[0 1] 6] [[3 5] 15]] [[[0 1] 6] [[4 5] 16]]]
   [[[[0 3] 4] [[4 5] 16]]]
   [[[[0 4] 3]]]
   [[[[0 5] 19]]]
   [[[[1 5] 13]]]
   [[[[2 3] 4] [[4 5] 16]]]
   [[[[2 4] 3]]]
   [[[[2 5] 19]]]
   [[[[3 5] 15]]]
   [[[[4 5] 16]]])
  Finally calculate which permutation provides the highest profit, which is 25 in this example."
  [k prices]
  {:pre [(> k 0) (every? number? prices)]}
  (let [ps           (profits prices)
        permutations (->> (iterate rest ps)
                          (take (count ps))
                          (map (partial non-overlapping-permutations k))
                          (map #(map (fn [x] (reduce + (map second x))) %))
                          (flatten))]
    (if (empty? permutations)
      0
      (apply max permutations))))