Skip to content

Instantly share code, notes, and snippets.

@idiomatic

idiomatic/longestIncreasingSubsequence.coffee

Created July 15, 2015 17:16
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 idiomatic/751b0e1593e08177b085 to your computer and use it in GitHub Desktop.
Save idiomatic/751b0e1593e08177b085 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
longestIncreasingSubsequence.coffee
longestIncreasingSubsequence = (sequence) ->
startIndex = []
endIndex = []
subsequences = []
for value, i in sequence
for length in [endIndex.length..0] by -1
if (sequence[endIndex[length - 1]] ? Number.MIN_VALUE) < value < (sequence[endIndex[length]] ? Number.MAX_VALUE)
endIndex[length] = i
startIndex[length] = startIndex[length - 1] ? i
subsequences[length] = [(subsequences[length - 1] ? [])..., value]
return [startIndex[startIndex.length - 1], endIndex[endIndex.length - 1], subsequences[subsequences.length - 1]]
sequence = [10, 3, 7, 9, 0, 15]
console.log(sequence)
console.log(longestIncreasingSubsequence(sequence))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment