dodo_optimization_problem.clj

(defn tree
  [arr]
  (if (empty? arr)
    []
    [[(tree (rest arr))]
     [(tree (reverse
              (rest
                (reverse arr))))]]))

(defn all-paths
  ([arr] (partition (dec (count arr))
                    (all-paths (tree arr) [])))
  ([tree path]
   (if (empty? (last tree))
     []
     (let [lpaths (all-paths (last (first tree)) (conj path :l))
           rpaths (all-paths (last (second tree)) (conj path :r))
           paths (concat lpaths rpaths)]
       (if (empty? paths)
         path
         paths)))))

(defn evaluate
  ([arr] (let [paths (all-paths arr)]
           (first
             (sort-by second
                      >
                      (map #(vector % (evaluate % arr 1)) paths)))))
  ([path arr depth]
   (if (empty? arr)
     0
     (let [curr (first path)
           value (if (= curr :l)
                   (first arr)
                   (last arr))
           path (rest path)
           arr (if (= curr :l)
                 (rest arr)
                 (reverse (rest (reverse arr))))]
       (+ (* depth value)
          (evaluate path arr (inc depth)))))))