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))

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?


2 Answers 2


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)))

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))

This function assumes a longs argument:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.