最大部分列和

市民講座でやってました。

;最大部分列和問題
;数列の中で和が最大となる、連続している部分列の和を求める
(def x [31,-41,59,26,-53,58,97,-93])

(defn sum [a b]
  (if (< 0 (+ a b)) (+ a b) 0))

(defn s
  ([coll-x]
   (s (next coll-x) (list (first coll-x))))
  ([coll-x coll-s]
   (loop [a coll-x b coll-s]
     (if (nil? a) b
       (recur (next a) (concat b (list (sum (last b) (first a)))))))))

(reduce max (s x))

上記のxの中での回答は、59〜97までの和,187になる。