SHARE
TWEET

Untitled

a guest May 18th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # Merge two optimal subsets
  2. meld = (a, b) ->
  3.   # Push all elements from b greater than
  4.   # last a
  5.   i = 0
  6.   last = a[a.length-1]
  7.   while b[i] < last
  8.     i++
  9.  
  10.   if b.length - i > 0
  11.     a.splice(a.length, 0, b.slice(i)...)
  12.  
  13.   # Check if b is larger overall
  14.   i = 0
  15.   first = b[0]
  16.   while a[i] < first
  17.     i++
  18.  
  19.   # Drop rest if b is longer
  20.   restLength = a.length - i
  21.   if b.length >= restLength
  22.     a.splice(i, restLength, b...)
  23.  
  24.   return a
  25.  
  26. LIS = (a) ->
  27.   # Consume to the right as much as we can
  28.   i = 1
  29.   while a[i] > a[i-1]
  30.     i++
  31.  
  32.   result = a.slice(0, i)
  33.  
  34.   # If we have something, merge it with the best of the rest
  35.   if result.length
  36.     meld result, LIS(a.slice(i))
  37.  
  38.   return result
  39.  
  40. LIS.meld = meld
  41.  
  42. module.exports = LIS
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top