# Merge two optimal subsets
meld = (a, b) ->
  # Push all elements from b greater than
  # last a
  i = 0
  last = a[a.length-1]
  while b[i] < last
    i++

  if b.length - i > 0
    a.splice(a.length, 0, b.slice(i)...)

  # Check if b is larger overall
  i = 0
  first = b[0]
  while a[i] < first
    i++

  # Drop rest if b is longer
  restLength = a.length - i
  if b.length >= restLength
    a.splice(i, restLength, b...)

  return a

LIS = (a) ->
  # Consume to the right as much as we can
  i = 1
  while a[i] > a[i-1]
    i++

  result = a.slice(0, i)

  # If we have something, merge it with the best of the rest
  if result.length
    meld result, LIS(a.slice(i))

  return result

LIS.meld = meld

module.exports = LIS