Skip to content

Instantly share code, notes, and snippets.

@STRd6
Last active August 29, 2015 14:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save STRd6/39d48e97a2a347004fb1 to your computer and use it in GitHub Desktop.
Save STRd6/39d48e97a2a347004fb1 to your computer and use it in GitHub Desktop.
Using integration to solve greatest contiguous sum problem
integrate = (array) ->
total = 0
array.map (n) ->
total += n
zeros = (array) ->
array.reduce (zeros, n, i) ->
if !(array[i-1] > 0) and n > 0
zeros.push i
, []
greatestContiguousSum = (array) ->
Sarray = integrate(array)
end = max(Sarray)
start = zeros(Sarray).filter (zero) ->
zero < end
.last()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment