More concise and/or idiomatic max subarray in Clojure?

Question

I've implemented the following two versions of the classic "Max Sub-Array" 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?

Answer 1

Great answer from Jean Niklas L'Orange on the Clojure Google Group:

(defn max-subarray [A]
 (let [pos+ (fn [sum x] (if (neg? sum) x (+ sum x)))
 ending-heres (reductions pos+ 0 A)]
 (reduce max ending-heres)))

Answer 2

I think your implementations are succinct and straightforward. However, I prefer using primitives for loop args to avoid auto-boxing:

(defn maximum-subarray
 [^longs ls]
 (loop [i 0, meh 0, msf 0] ; index, max-ending-here, max-so-far
 (if (< i (alength ls))
 (recur (inc i) (max (+ meh (aget ls i)) 0) (max msf meh))
 msf)))

This function assumes a longs argument:

user> (def a (long-array [31 -41 59 26 -53 58 97 -93 -23 84]))
#'user/a
user> (maximum-subarray a)
187