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 max-sum [xs]
  (reduce max (reductions #(max 0 (+ %1 %2)) 0 xs)))

@steffan-westcott I have a passing familiarity with Clojure, so sorry if this seems really basic. Given xs=[3 -6 2 4 -2 7 -9], what would %1 and %2 be, if you were to step through the function? I've been trying to see how Kotlin works, and I'm trying to see if I can write it there in a similar manner, but I can't really understand what your function is doing in the first place.

@mattfara #( ) is an anonymous function which takes arguments %1, %2 etc. reductions is similar to reduce, in that %1 is the "accumulated" value and %2 is each value of the input sequence in turn. So the reductions in the selected example are:

(max 0 (+  0  3))  ; =>  3
(max 0 (+  3 -6))  ; =>  0
(max 0 (+  0  2))  ; =>  2
(max 0 (+  2  4))  ; =>  6
(max 0 (+  6 -2))  ; =>  4
(max 0 (+  4  7))  ; => 11
(max 0 (+ 11 -9))  ; =>  2

The algorithm keeps a running total of numbers seen so far, but starting over at 0 if the total goes negative. The desired result is the maximum total seen overall.

@steffan-westcott great! Thank you for explaining. With your help, I got it to work in Kotlin. Clojure is a beautiful language. I hope I can learn to think in these terms, even if I'm using Kotlin.
listOf(3, -6, 2, 4, -2, 7, -9) .runningFold(0){ acc,n -> maxOf(0,acc+n) } .maxOrNull()

Solution in Haskell-

maxSum :: (Ord a, Num a) => [a] -> a
maxSum =
  maximum
  . scanl (\x -> max 0 . (+ x)) 0

main :: IO ()
main = do
  print $ maxSum []
  print $ maxSum [-1]
  print $ maxSum [2]
  print $ maxSum [1, 10]
  print $ maxSum [3, -6, 2, 4, -2, 7, -9]

Solution in python-

from itertools import chain, accumulate

def maxSum(xs):
    return max(
        accumulate(
            chain([0], xs),
            lambda x, y: max(x + y, 0),
        )
    )
    
if __name__ == "__main__":
    print(maxSum([]))
    print(maxSum([-10]))
    print(maxSum([1, 10]))
    print(maxSum([1, -5, 20, 30, -10, 100]))

Solution in python (Imperative)-

def maxSum(xs):
    max_s = s = 0
    for x in xs:
        s = max(s + x, 0)
        max_s = max(max_s, s)
    return max_s
    
if __name__ == "__main__":
    print(maxSum([]))
    print(maxSum([-10]))
    print(maxSum([1, 10]))
    print(maxSum([1, -5, 20, 30, -10, 100]))

(defn max-sum [s]
  (->>
    (map (fn [i s1] [i s1]) (range) (take (count s) (repeat s)))
    (map (fn [[i s1]] (drop i s1)))
    (map (fn [s2]
           (->>
             (map (fn [i s3] [i s3]) (range) (take (inc (count s2)) (repeat s2)))
             (map (fn [[i s3]] (take i s3)))
             (map (fn [s3] (apply + s3)))
             (reduce max))))
    (reduce max 0)))

@steffan-westcott That's an elegant use of reductions!

Here's a less elegant solution using partition:

(defn max-sum [xs]
  (->> (range (inc (count xs)))
       (mapcat #(partition % 1 xs))
       (map (partial apply +))
       (apply max 0)))

(defn sums [numbers start-idx]
  "Returns a vector of all possible sums for `start-idx`."
  (for [i (range start-idx (count numbers))
        j (range i (count numbers))]
    (->> (subvec numbers i (inc j)) 
         (apply + ))))

(defn max-sum [numbers]
  (let [numbers (-> (vec numbers)
                    (conj 0))
        sums (->> (for [i (range (count numbers))] (sums numbers i))
                  flatten)]
    (apply max  sums)))

For anyone interested, the canonical linear-time solution to this is Kadane's algorithm, implemented really nicely by @steffan-westcott. I'd done this problem in imperative code on some Leetcode-style site somewhere, but looking at your solution I feel like I finally "got" something I've read in FP books but have struggled to figure out when and how to use the concept.

Basically, the imperative version loops through the list and keeps track of the maximum sum seen so far by doing a calculation at each iteration of the loop and then examining and mutating a variable. My initial Clojure solution did something similar using reduce, but kinda-sorta just hid the mutable state inside the accumulator used by the reducing function:

(defn reducer-old [{highest :highest current :current} next-num]
  (let [new-current (max next-num (+ current next-num))]
    {:current new-current :highest (max highest new-current)}))

(defn max-sub-sum-old [nums]
  (->> nums
       (reduce reducer-old {:highest (Integer/MIN_VALUE) :current (Integer/MIN_VALUE)})
       :highest))

But now I get it -- express those intermediate calculations as a collection of values, and then that collection can be run through another pure function that applies the same logic that would have been used to mutate state at different points in time. That's pretty cool.

And if I can add one thing to the solution, here's a variation that handles a list without any positive numbers:

(defn max-to-here [acc current]
  (max (+ acc current) current))

(defn max-sum [nums]
  (reduce max (reductions max-to-here Integer/MIN_VALUE nums)))

(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)))