js_test.js

// Given a integer n, output the first n numbers of the Fibonacci sequence efficiently. 

// Input: 5
// Output: [1, 1, 2, 3, 5]

function fib(n) {
  if (n < 2) {
    return 1;
  }
  
  var fib = [1, 1];
  for (var i = 2; i < n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }
  return fib;
}

fib(5);

// Given a list of integers, output the length of the longest increasing sequence of integers within the list in at most O(n) time.

// Input: [2, 1, 2, 3, 4, 5]
// Output: 5 (longest increasing sequence of integers is 1 2 3 4 5 because 2->1 is decreasing)

// Input: [7, 4, 6, 10, 11, -2, 0, 4]
// Output: 4 (longest increasing sequence of integers is 4 6 10 11)
a = [1, 4];
b = [1, 4, 4];
c = [1, 4, 4, 4];
d = [1, 4, 4, 4, 4];
e = [1, 4, 4, 4, 4, 4];
f = [2, 1, 2, 5, 5];
g = [7, 6, 1, 2, 3, 8, 8];
h = [7, 6, 5, 5, 1, 2, 3, 4];
i = [1, 1, 1];
j = [1, 3, 3, 3, 3, 5];
k = [1, 3, 3, 3, 3, 5, 6, 6];

function getIncSeq(arr) {
  var temp = [];
  var final = [];
  var len = arr.length;

  temp.push(arr[0]);
  for (var i = 1, j = 0; i <= len; i++) {
    if (arr[i] > temp[j]) {
      temp.push(arr[i]);
      j++;
    }else {
      if (temp.length > 0) {
        final.push(temp);
        temp = [];
        temp.push(arr[i]);
        j = 0;
      }
    }
  }
  return final;
}

function _findLargestIncSeq(arr) {
  var len = arr.length;
  var _largest = 0;

  for (var i = 0; i < len; i++) {
    var _len = arr[i].length;
    _largest = _largest > _len ? _largest : _len;
  }

  return _largest;
}


console.log(a);
console.time('a');
console.log(_findLargestIncSeq(getIncSeq(a)));
console.timeEnd('a');
console.log('++++++++\n');

console.log(b);
console.time('b');
console.log(_findLargestIncSeq(getIncSeq(b)));
console.timeEnd('b');
console.log('++++++++\n');

console.log(c);
console.time('c');
console.log(_findLargestIncSeq(getIncSeq(c)));
console.timeEnd('c');
console.log('++++++++\n');

console.log(d);
console.time('d');
console.log(_findLargestIncSeq(getIncSeq(d)));
console.timeEnd('d');
console.log('++++++++\n');

console.log(e);
console.time('e');
console.log(_findLargestIncSeq(getIncSeq(e)));
console.timeEnd('e');
console.log('++++++++\n');

console.log(f);
console.time('f');
console.log(_findLargestIncSeq(getIncSeq(f)));
console.timeEnd('f');
console.log('++++++++\n');

console.log(g);
console.time('g');
console.log(_findLargestIncSeq(getIncSeq(g)));
console.timeEnd('g');
console.log('++++++++\n');

console.log(h);
console.time('h');
console.log(_findLargestIncSeq(getIncSeq(h)));
console.timeEnd('h');
console.log('++++++++\n');

console.log(i);
console.time('i');
console.log(_findLargestIncSeq(getIncSeq(i)));
console.timeEnd('i');
console.log('++++++++\n');

console.log(j);
console.time('j');
console.log(_findLargestIncSeq(getIncSeq(j)));
console.timeEnd('j');
console.log('++++++++\n');

console.log(k);
console.time('k');
console.log(_findLargestIncSeq(getIncSeq(k)));
console.timeEnd('k');
console.log('++++++++\n');