Hand crafted longest common sub sequence

I know that the below solution is not the best one and I am in the way to learn that stuff till then I have applied the brute force to see how far I can go with my intuition.

console.clear();

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

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

function map(xs, cb) {
  return [].map.call(xs, cb);
}

function powerset(xs) {
  if (xs.length === 0) return [[]];
  var res = powerset(allButLast(xs));

  return res.concat(map(res, function(el) { return el.concat(last(xs)); }));
}

console.log(powerset([]));           // [[]]
console.log(powerset([1]));          // [[], [1]]
console.log(powerset([1, 2]));       // [[], [1], [2], [1, 2]]
console.log(powerset([1, 2, 3]));    // [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

function increasing(xs) {
  var i = 1,
      l = xs.length;
  for (;i  res.length) res = subset;
  });
  return res;
}

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

I have tried to be as much naive as possible because sometimes the best solution doesn't come to your mind most probably in the case of interview etc. I need to know if the code is clear and readable?

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 > 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] > largestSequenceLength ){
largestSequenceLength = indexes[n];
lastIntegerofLargestSequence = n;
}
}

for( var i = lastIntegerofLargestSequence - largestSequenceLength + 1; i

StackExchange Code Review Q#138455, answer score: 3