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:
- Start a sequence with the first element of the input array
- 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.
- 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