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