Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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]) ;=> 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/

@steffan-westcott

This comment has been minimized.

Copy link

@steffan-westcott steffan-westcott commented Aug 9, 2021

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

@steffan-westcott steffan-westcott commented Aug 9, 2021

@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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

@Sinha-Ujjawal Sinha-Ujjawal commented Aug 10, 2021

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]))
@Sinha-Ujjawal

This comment has been minimized.

Copy link

@Sinha-Ujjawal 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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

@KingCode 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)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment