/**
 * LIS = Longest increasing subsequence.
 * Input = [10, 22, 9, 33, 21, 50, 41, 60, 80]
 * Output = [10, 22, 33, 50, 60, 80]
 * Created by gaurav on 1/7/15.
 */


function findSubsequence(arr){
    var allSubsequence = [],
        longestSubsequence = null,
        longestSubsequenceLength = -1;

    for(var i=0;i<arr.length;i++){          //i=1
        var subsequenceForCurrent = [arr[i]],
            current = arr[i],
            lastElementAdded = -1;
        for(var j=i;j<arr.length;j++){
            var subsequent = arr[j];
            if((subsequent > current) && (lastElementAdded<subsequent)){
                subsequenceForCurrent.push(subsequent);
                lastElementAdded = subsequent;
            }
        }
        allSubsequence.push(subsequenceForCurrent);
    }
    for(var i in allSubsequence){
        var subs = allSubsequence[i];
        if(subs.length>longestSubsequenceLength){
            longestSubsequenceLength = subs.length;
            longestSubsequence = subs;
        }
    }
    return longestSubsequence;
}


(function driver(){
    var sample = [87,88,91, 10, 22, 9,92, 94, 33, 21, 50, 41, 60, 80];
    console.log(findSubsequence(sample));
})();

lastElementAdded = -1;

[ 87, 88, 91, 92, 94 ]
[ 88, 91, 92, 94 ]
[ 91, 92, 94 ]

function findLongestIncreasingSequence(array) {
  var sequence = [],
      fork = null;

  // Always add the first value to the sequence
  sequence.push(array[0]);

  // Reduce the array with. Since no initial accumulator is given,
  // the first value in the array is used
  array.reduce(function (previous, current, index) {

    // If the current value is larger than the last, add it to the
    // sequence and return (i.e. check the next value)
    if(current > previous) {
      sequence.push(current);
      return current;
    }

    // If, however, the value is smaller, and we haven't had a fork
    // before, make one now, starting at the current value's index
    if(!fork && current < previous) {
      fork = findLongestIncreasingSequence(array.slice(index));
    }

    // Return the previous value if the current one is less or equal
    return previous;
  });

  // Compare the current sequence's length to the fork's (if any) and
  // return whichever one is larger
  return fork && fork.length > sequence.length ? fork : sequence;
}

findLongestIncreasingSequence(sample); // => [ 87, 88, 91, 92, 94 ]

Initial input: 87  88  91  10  22  9  92  94  33  21  50  41  60  80
====================================================================
1st call:       √   √   √   F   .  .   √   √   .   .   .   .   .   .
2nd call:                   √   √  F   √   √   .   .   .   .   .   .
3rd call:                          √   √   √   F   .   .   .   .   .
4th call:                                      √   F   √   .   √   √
5th call:                                          √   √   F   √   √
6th call:                                                  √   √   √

let max_ref=1;

function longestIncreasingSubsequence(arr,n) {

   if (n == 1)
       return 1;
   var res, max_ending_here = 1;

    for (var i = 1; i < n; i++)
    {
        res = longestIncreasingSubsequence(arr,i);
        if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)
            max_ending_here = res + 1;
    }
    if (max_ref < max_ending_here)
       max_ref = max_ending_here;

    return max_ending_here;
}

let result = longestIncreasingSubsequence(arr,arr.length);