current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 2 down vote favorite

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?

share|improve this question
up vote 1 down vote accepted

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)))
share|improve this answer
up vote 0 down vote

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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