6
\$\begingroup\$

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));
})();
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ But, wouldn't the LIS be [10,22,33,50,60,80]? \$\endgroup\$ – Trees4theForest Feb 22 '18 at 1:29
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Scott Sauyet Jul 25 '17 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.