StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I made a quick and dirty JavaScript implementation (note: it is O(n^2)):</p> <pre><code>function lis(a) { var tmpArr = Array(), result = Array(), i = a.length; while (i--) { var theValue = a[i], longestFound = tmpArr[theValue] || 1; for (var j=theValue+1; j<tmpArr.length; j++) { if (tmpArr[j] >= longestFound) { longestFound = tmpArr[j]+1; } } result[i] = tmpArr[theValue] = longestFound; } return result; } </code></pre> <p><strong>jsFiddle:</strong> <a href="http://jsfiddle.net/Bwj9s/1/" rel="nofollow">http://jsfiddle.net/Bwj9s/1/</a></p> <p>We run through the array right-to-left, keeping previous calculations in a separate temporary array for subsequent lookups.</p> <p>The <code>tmpArray</code> contains the previously found subsequences beginning with any given value, so <code>tmpArray[n]</code> will represent the longest subsequence found (to the right of the current position) beginning with the value <code>n</code>.</p> <p>The loop goes like this: For every index, we look up the value (and all higher values) in our <code>tmpArray</code> to see if we already found a subsequence which the value could be prepended to. If we find one, we simply add 1 to that length, update the <code>tmpArray</code> for the value, and move to the next index. If we don't find a working (higher) subsequence, we set the <code>tmpArray</code> for the value to 1 and move on.</p> <hr> <p>In order to make it O(n log n) we observe that the <code>tmpArray</code> will always be a decreasing array -- it can and should use a binary search rather than a partial loop.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload