See: http://careercup.com/question?id=11070934

largest-subseq.js

//
// See: http://careercup.com/question?id=11070934
//
// Given an array which might contain duplicates, find
// largest subset of it which forms subsequence
//
// Input: [1, 6, 10, 4, 7, 9, 5]
// Output: [4, 5, 6, 7]
//

const logMergesToConsole = true;

/**
 * @param {array} list - The list to search
 * @return {array} - The largest subsequence
 */
const largestSubseq = list => {
  // handle base cases
  if (list.length <= 1) {
    return list;
  }
  // prep the data
  let seqs = [];
  for (let i = 0; i < list.length; i++) {
    seqs.push({
      seq: [list[i]],
      start: list[i],
      end: list[i]
    });
  }
  // merge subsequences
  let mergedSeqs = mergeSeqs(seqs);
  // find largestSeq
  let largestSeq = [];
  for (let i = 0; i < mergedSeqs.length; i++) {
    if (mergedSeqs[i].seq.length > largestSeq.length) {
      largestSeq = mergedSeqs[i].seq;
    }
  }
  return largestSeq;
};

/**
 * Merge an array of sequences
 *
 * @param {array} seqs - The seqs to merge
 * @return {array} - Array with all seqs merged
 */
const mergeSeqs = seqs => {
  return seqs.reduce((acc, curr, i, arr) => {
    let mergeable = false;
    for (let j = 0; j < acc.length; j++) {
      // case: mergeable as curr->acc[j]
      if (curr.start === acc[j].start - 1) {
        if (logMergesToConsole) {
          console.log('case: mergeable as curr->acc[j]', curr);
        }
        acc[j].seq.unshift(curr.seq[0]);
        acc[j].start = curr.start;
        // recursively merge
        acc = mergeSeqs(acc);
        mergeable = true;
      }
      // case: mergeable as acc[j]->curr
      if (curr.end === acc[j].end + 1) {
        if (logMergesToConsole) {
          console.log('case: mergeable as acc[j]->curr', curr);
        }
        acc[j].seq.push(curr.seq[curr.seq.length - 1]);
        acc[j].end = curr.end;
        // recursively merge
        acc = mergeSeqs(acc);
        mergeable = true;
      }
      // case: unmergeable
      if (logMergesToConsole) {
        console.log('case: unmergeable', curr);
      }
    }
    if (!mergeable) {
      acc.push(curr);
    }
    return acc;
  }, [seqs.shift()]); // remove and return first element
}