(ns max-subarray
  (:require [clojure.test :refer [deftest is]]))

(defn propagating
  "Transducer that emits the current maximum value, according to cmp"
  [init cmp]
  (fn [rf]
    (let [cur-max (volatile! init)]
      (completing
       (fn [acc nxt]
         (vswap! cur-max cmp nxt)
         (rf acc @cur-max))))))

(defn max-sequence [xs]
  (-> (into [0]
            (comp (propagating 0 (comp #(max 0 %) +)) ;; Maintain the running sum, as long as it's non-zero
                  (propagating 0 max))                ;; Emit the current maximum running sum
            xs)
      peek)) ;; Get the last maximum running sum (peek on vector makes this fast)

(deftest simple
  (is (= (max-sequence  [-2, 1, -3, 4, -1, 2, 1, -5, 4]) 6))
  (is (= (max-sequence  []) 0))
  (is (= (max-sequence  [1 2 3 4]) 10))
  (is (= (max-sequence  [-1 -2 -3 -4]) 0))

  )

(defn collect-runs [eq]
  (let [sentinel (Object.)]
    (fn [rf]
      (let [c-v (atom sentinel)
            current (atom [])]
        (fn
          ([] (rf))
          ([acc] (rf (rf acc @current)))
          ([acc nxt]
           (when (= @c-v sentinel)
             (reset! c-v nxt))
           (let [result (if (eq @c-v nxt)
                          (do (swap! current conj nxt)
                              acc)
                          (let [r (rf acc @current)]
                            (reset! current [nxt])
                            r))]
             (reset! c-v nxt)
             result)))))))

(defn series-sum [n]
  (format "%.2f" (double (apply + (map #(/ 1.0 (doto % prn)) (take n (iterate #(+ % 3.0) 1.0)))))))