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