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/
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: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: