I've implemented the following two versions of the classic "Max Sub-Array" problem in Clojure, using the Kadane algorithm.
(defn max-sub-array [A] (loop [x (first A) a (rest A) max-ending-here 0 max-so-far 0] (if (seq a) (recur (first a) (rest a) (max x, (+ max-ending-here x)) (max max-so-far, max-ending-here)) max-so-far)))
(defn max-sub-array-reduction [A] (letfn [(find-max-sub-array [[max-ending-here max-so-far] x] [(max x (+ max-ending-here x)) (max max-so-far max-ending-here)])] (second (reduce find-max-sub-array [0 0] A))))
Is there a more concise implementation, perhaps using
filter or merely by making the
reduce version more "idiomatic" somehow?