Longest increasing subsequence part II

Question

Using the answer provided here, I am now trying to find the longest increasing subset in two different sequences of numbers defined by location1 and location2.

For each location there are 16 readings. Each reading has its own position. I have sorted both lists by the Reading column.

Using a Scatter-Plot graph for each location, I am trying to find the longest increasing subset

Location 1

Location 2

Based on the two graphs; for location 1 the length of the longest increasing subset is 7 (7 positions) and for location 2 it is 5.

I highlighted the longest subsequence I found using the graph in blue and Itzik's subsequence in red.

The problem is that the book that I took these two lists from TSQL Querying (Itzik Ben-Gan) indicates that the longest increasing subset for Location2 has 6 points and using the graph, I only found 5 points that make up the longest subset.

Here is the longest subset according to the book

As you can see the readingNum column is out of order. My assumption was that to find the longest increasing subset, the position in the array had to increase as well as the value of that position.

Questions:

What is the longest increasing subsequence for both locations?

What is the formula, algorithm or method used?

Thanks

Answer 1

First, to give proper credit, Chapter 5: Algorithms and Complexity, was written by Steve Kass. Regarding your question about the Length of the Longest Increasing Subsequence; note that the algorithm described in the book does not attempt to find the longest increasing subsequence but rather its length. Don't be confused by the specific values that the solution stores in the table variable. For example, here's a 6-point subsequence of increasing values for location 2:

1 - 3.894 3 - 3.939 5 - 3.940 10 - 4.035 12 - 4.086 13 - 4.093

Again, the values stored in the table variable are different, but their count is 6--the length of the longest increasing subsequence.

Cheers, Itzik

Answer 2

Itzik just emailed me to let me know you'd asked this question. As he points out, the algorithm in T-SQL Querying doesn't reveal the subsequence itself. It only reveals its length. The intermediate values appearing during the calculation don't necessarily help you find the actual sequence. (The algorithmic complexity of finding an actual longest subsequence is greater than for finding the length.)

If you want to learn a bit more about the algorithm than what's in T-SQL Querying, see my 2002 article from SQL Server Magazine, available online here.

Relational algebra isn't central to this interesting mathematical problem (finding the length of the longest increasing subsequence), but it turned out to be useful in the real world, and a SQL solution turned out to be valuable.