I've implemented the following two versions of the "Max Sub-Array" problem
(http://en.wikipedia.org/wiki/Maximum_subarray_problem) in Clojure, using
the Kadane algorithm.
First with `loop` / `recur`
(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)))
Then with `reduce`
(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?
Also posted here:
http://codereview.stackexchange.com/questions/15992/more-concise-and-or-idiomatic-max-subarray-in-clojure
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
