2
\$\begingroup\$

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?

\$\endgroup\$

2 Answers 2

Reset to default
1
\$\begingroup\$

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)))
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.