Hand crafted longest common sub sequence
Interesting question,

I would say for an interview, if you are given a task and you think you need combinations or permutations, then there is a good chance it's a trick question. Those are terrible for performance and I would avoid them as the plague during interviews.

Secondly, your code is hard to read. Only because of the comment on the very last line did things come together for me.

Other than that;


Try to be consistent 

function allButLast(arr) {
  return arr.slice(0, arr.length - 1);
}

function last(xs) {
  return xs.slice(-1);
}


These functions both get an array, but in one the argument is called arr, in the other one xs. They should have the same name, I would go for list.
I like your powerset routine, and might borrow it
I dont understand [].reduce.call in sum, why not just xs.reduce ? From an interview perspective it makes me think you dont understand how reduce works :/


On the whole this implementation should be light years faster, though I only tested it with your test case which I got right the first time, so I have good hopes ;)



console.log(LIS([2, 3, 1, 4, 0, 5])); // [2, 3, 4, 5]

//Find the longest common sub sequence
function LIS( list ){

  var indexes = {},
      //Possibly too verbose variable name ;)
      lastIntegerofLargestSequence,
      largestSequenceLength = 0,
      output = [];
     
  for( n of list ){
    
    //Have we processed a predecessor yet?
    if( indexes[n-1 ] !== undefined ){
      //There is a predecessor, if we have never found n,
      //then put n with predecessor's length + 1
      if( indexes[n] === undefined ){
        indexes[n] = indexes[n-1] + 1;
      //Otherwise ONLY put that predecessor length + 1
      //if that would make a better (longer sequence)  
      }else if( indexes[n-1] + 1 &gt; indexes[n]  ){
        indexes[n] = indexes[n-1] + 1;      
      }
      //First number in a possible sequence
    }else if( indexes.n === undefined ){ //That 0 ;/
      indexes[n] = 1;
    } 
    
    //Keep track of the largest sequence
    if( indexes[n] &gt; largestSequenceLength ){
      largestSequenceLength = indexes[n];
      lastIntegerofLargestSequence = n;
    }
  }

  for( var i = lastIntegerofLargestSequence - largestSequenceLength + 1; i &lt;= lastIntegerofLargestSequence ; i++ )
    output.push(i);
  
  console.log(output)

}