Longest Increasing Subsequence

Question

I am learning dynamic programming and I have written down some code for longest increasing subsequence. I would like to know if there is any case or any area of improvement in the terms of optimization/programming style.

/**
 * 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));
})();

Answer 1

This bit worries me:

lastElementAdded = -1;

It assumes that the minimum value in the array is zero. But really, an increasing sequence could start with -3456780 or something.

I'd use null or something non-numeric instead. Or simply add the first element automatically, and start the loop at index 1. You could use Number.NEGATIVE_INFINITY, but it has the same problem: A sequence could start at negative infinity.

Also, don't use for..in loops on arrays. A for..in loop enumerates an object's properties; it's not intended for iterating through an array's elements. Instead, use a regular for loop, or a forEach iterator.

Lastly, I'd change allSubsequence to allSubsequences (plural) simply because it more grammatically correct.

In terms of overall strategy, your current algorithm is doing a bit of unnecessary work. Given the example input, the first 3 subsequences it finds are:

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

The last two aren't really interesting, since they're just subsequences of the first.

Now, this really isn't a problem for arrays as short as what you've got here. Still, it's a fun exercise, so I tried my hand at it. There's probably an even more elegant solution than what I'm proposing here, though. Algorithms aren't my strong suit, I'm afraid. But here's what I came up with:

1. Start a sequence with the first element of the input array
2. Iterate through the array
   • If a value is greater than the sequence's maximum, append it to sequence
   • If it's less and it's the first such value we've found, recurse with a subset of the input array, starting at the current index. Store the result.
3. Return whichever sequence - the current one, or the "fork" - is longer

Kinda hard to explain, actually. Hope the code below will help illustrate:

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;
}

Given the example input, you get:

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

Anyway, what it does is more or less this, where √ means the value was added to a sequence, and F means it "forked" and recursed

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: √ √ √

Unfortunately, it's not tail-recursive, so call stack depth could be an issue.

And there's probably more optimizations that can be made. For instance, if the current sequence is already 5 items long, there's no reason to fork if the array only has 4 items left. And as I said, there's probably an even cleverer solution overall.

The alternative to the above would be to simply map out the indices at which a value is lower than the one preceding it. Then do the same thing (slice the array at those indices, find increasing sequence) one at a time instead of recursively, and compare sequence lengths at the end. Same result. But recursion is more fun :P

• Trees4theForest: But, wouldn't the LIS be [10,22,33,50,60,80]?

Answer 2

You might easily do this job by a very simple tail call optimized recursive function or by Array.prototype.reduce() functor.

function lis(a, r = [a[0]]){
 if(!a.length) return r;
 a.splice(0,1);
 r[r.length-1] < a[0] && r.push(a[0]);
 return lis(a,r);
} 
var arr = [-7, -10, 6, 22, 9, 33, 21, 50, 41, 60, 80 ];
console.log(lis(arr));

Or like

var arr = [-7, -10, 6, 22, 9, 33, 21, 50, 41, 60, 80 ],
 lis = arr.reduce((p,c,i) => i ? p[p.length-1] < c ? p.concat(c)
 : p
 : [c] ,[]);
console.log(lis);

• Scott Sauyet: The easiest way to see that this does not generate the longest increasing subsequence is to put, say, -8 between -10 and 6 in that list. It will generate the same result, but the subsequence starting {-10, -8, 6, 22...} is longer.