438 PurelyFunctional.tv Newlsetter

00 Maximum sum.md

Maximum sum

Write a function that returns the maximum sum of a contiguous subsequence of integers in a vector.

Examples

(max-sum []) ;=> 0 ; (sum of empty seq is 0)
(max-sum [1]) ;=> 1
(max-sum [1 10]) ;=> 11
(max-sum [-1]) ;=> 0 (because you can choose the empty subsequence, which has sum 0)
(max-sum [3 -6 2 4 -2 7 -9]) ;=> 11 (sum of [2 4 -2 7])

They say you can do it in linear time and constant space. Just make sure it works with large vectors.

Thanks to this site for the problem idea, where it is rated Expert in JavaScript. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

(defn windows 
  "Constructs a seq of all contiguous subsequences of xs."
[xs]
  (let [siz (count xs) 
        step (fn [subs n]
               (if (< siz n)
                 subs
                 (recur (conj subs (take n xs))
                        (inc n))))]
    (if (empty? xs)
      #{[]}
      (-> (windows (drop 1 xs))
          (into (step #{} 0))))))

(defn max-sum [xs]
  (->> xs  windows
       (map #(if (empty? %) 0
                 (apply + %)))
       (apply max)))