Javascript function for finding the longest increasing subsequence within a sequence of numbers (stored as an array) . Also included is a derivative function which finds the longest decreasing sequence.

longestIncreasingSequence

// 
// longestIncreasingSequence
// ---
//
// Javascript function for finding the longest increasing subsequence within a sequence of numbers
//
// @param {Array} arr  The array containng the sequence
// @param {Boolean} strict  Boolean specifying whether to use strict (`<`) inequality (default is to use `<=`)
// @return {Array}
//
function longestIncreasingSequence(arr, strict) {

    var index = 0,
      indexWalker,
    	longestIncreasingSequence,
    	i,
    	il,
    	j;

    // start by putting a reference to the first entry of the array in the sequence
    indexWalker = [index];
    	
    // Then walk through the array using the following methodolgy to find the index of the final term in the longestIncreasing and
    // a sequence (which may need altering later) which probably, roughly increases towards it - http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
	for (i = 1, il = arr.length; i < il; i++) {
		
        if (arr[i] < arr[indexWalker[index]]) {
         	
         	// if the value is smaller than the last value referenced in the walker put it in place of the first item larger than it in the walker
        	for (j = 0; j <= index; j++) {

            	// As well as being smaller than the stored value we must either 
            	// - be checking against the first entry
            	// - not be in strict mode, so equality is ok
            	// - be larger than the previous entry
                if (arr[i] < arr[indexWalker[j]] && (!strict || !j || arr[i] > arr[indexWalker[j-1]])) {
                    indexWalker[j] = i;
                    break;
                }
            }

        // If the value is greater than [or equal when not in strict mode) as the last in the walker append to the walker
        } else if (arr[i] > arr[indexWalker[index]] || (arr[i] === arr[indexWalker[index]] && !strict))  {
            indexWalker[++index] = i;
        }
		
    }

    // Create an empty array to store the sequence and write the final term in the sequence to it
	longestIncreasingSequence = new Array(index + 1);
	longestIncreasingSequence[index] = arr[indexWalker[index]];


	// Work backwards through the provisional indexes stored in indexWalker checking for consistency
	for (i = index - 1; i >= 0; i--) {

		// If the index stored is smaller than the last one it's valid to use its corresponding value in the sequence... so we do  
		if (indexWalker[i] < indexWalker[i + 1]) {
            longestIncreasingSequence[i] = arr[indexWalker[i]];

        // Otherwise we need to work backwards from the last entry in the sequence and find a value smaller than the last entry 
        // but bigger than the value at i (this must be possible because of the way we constructed the indexWalker array)
        } else {
            for ( j = indexWalker[i + 1] - 1; j >= 0; j--) {
                if ((strict && arr[j] > arr[indexWalker[i]] && arr[j] < arr[indexWalker[i + 1]]) || 
                	(!strict && arr[j] >= arr[indexWalker[i]] && arr[j] <= arr[indexWalker[i + 1]]) ){
                    longestIncreasingSequence[i] = arr[j];
                    indexWalker[i] = j;
                    break;
                }
            }
        }
    }

    return longestIncreasingSequence;
}


// 
// longestDecreasingSequence
// ---
//
// Javascript function for finding the longest decreasing subsequence within a sequence of numbers
//
// @param {Array} arr  The array containng the sequence
// @param {Boolean} strict  Boolean specifying whether to use strict (`>`) inequality (default is to use `>=`)
// @return {Array}
//
function longestDecreasingSequence(arr, strict) {
  return longestIncreasingSequence(arr.reverse(), strict).reverse();
}