{{ message }}

Instantly share code, notes, and snippets.

# ericnormand/00 Maximum sum.md

Created Aug 9, 2021
438 PurelyFunctional.tv Newlsetter

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

### steffan-westcott commented Aug 9, 2021

 ```(defn max-sum [xs] (reduce max (reductions #(max 0 (+ %1 %2)) 0 xs)))```

### mattfara commented Aug 9, 2021

 @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.

### steffan-westcott commented Aug 9, 2021 • edited

 @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.

### mattfara commented Aug 9, 2021

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

### Sinha-Ujjawal commented Aug 10, 2021

 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  print \$ maxSum [1, 10] print \$ maxSum [3, -6, 2, 4, -2, 7, -9]```

### Sinha-Ujjawal commented Aug 10, 2021

 Solution in python- ```from itertools import chain, accumulate def maxSum(xs): return max( accumulate( chain(, 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]))```

### Sinha-Ujjawal commented Aug 10, 2021

 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]))```

### mcuervoe commented Aug 10, 2021

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

### safehammad commented Aug 11, 2021

 @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)))```

### vpetruchok commented Aug 11, 2021

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

### celebrimbor379 commented Aug 14, 2021

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

### KingCode commented Oct 3, 2021

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