Given the sequence, find the largest “reverse ordered” subsequence

Question

(yes, I searched as much as I can ...) Maybe I shouldn't use the sequence, but there is no better way to describe it.

[wording: As indicated in the response section, a subsequence is not a correct description. A pair of numbers are the right words!]

Define a sequence of numbers and determine the size of a pair of numbers from the sequence as the distance between two numbers. Obviously, the largest pair is [first number, last number]. The question is to find the largest pair of numbers with the order opposite to the pair [first, last].

For example, if the sequence is {1,6,3,5,2,8} , then the answer should be [6,2] , since the order [1,8] increases and the largest pair with decreasing order is [6,2] .

The question is, can this be resolved declaratively using SQL-like statements? In particular, I am thinking about using LINQ for this.

Thanks.

Answer 1

This is not a problem that is suitable for SQL. It is also poorly worded. You are really looking for pairs of numbers, not subsequences, and size is the distance between them.

It can be solved O (n) by scanning the sequence backward for the smallest number after a given point and its position. This yields {1,2,2,2,2,8) and {0,4,4,4,4,5} . Then, scanning this in parallel with the original sequences gives the dimensions {0,3,2,1,0,0} , so the largest size is for the pair (6,2) , the size of which is 3.

Answer 2

Unconfirmed, but I would try the following:

 var sequence = new[] {1, 6, 3, 5, 2, 8}; var isGoingUp = sequence.First() < sequence.Last(); //if the first sequence is going up, invert the sign on the sequence //this way we can always compare using "<" var sequenceToCheck = sequence.Select(x => isGoingUp ? -x : x).ToList(); //initial values int currentLength = 1; //the length of the subsequence found int startIndex = 0; //the starting index of the subsequence //check for each item longest subsequence for (int i = 0; i < sequenceToCheck.Count; i++) { //go from the end towards the beginning and find the longest sequence for i for (int j = sequenceToCheck.Count - 1; i > j; i--) { if (sequenceToCheck[i] < sequenceToCheck[j]) { //found i longest subsequence if (currentLength < j - i + 1) { startIndex = i; currentLength = j - i + 1; } break; //don't check any smaller sequences for i } } if(sequenceToCheck.Count - i < currentLength) break; //no need to check any more, no sequence past this can be longer } var subsequence = sequence.Skip(startIndex).Take(currentLength); 

You can also implement this solution in LINQ by calculating the distances from each point to the corresponding number (from the end).

---

Implementing this in SQL, however, will be a little more complicated, although you can do it. Here is my attempt and working SQL Fiddle example :

 WITH firstValue AS ( SELECT TOP 1 value FROM t ORDER BY id ), lastValue AS ( SELECT TOP 1 value FROM t ORDER BY id DESC ), seqToCheck AS ( SELECT id, CASE WHEN lastValue.value > firstValue.value THEN 0-t.value ELSE t.value END AS value FROM t CROSS JOIN firstValue CROSS JOIN lastValue ), subSequences AS ( SELECT s1.id, COALESCE(MAX(s2.id - s1.id + 1),1) AS distance FROM seqToCheck AS s1 LEFT JOIN seqToCheck AS s2 ON s1.value < s2.value AND s2.id > s1.id GROUP BY s1.id ), longestSubSequence AS ( SELECT TOP 1 id, distance FROM subSequences ORDER BY distance DESC ) SELECT t.value FROM t INNER JOIN longestSubSequence AS l ON t.id >= l.id AND t.id < l.id + l.distance ORDER BY t.id 

This assumes that you have a growing column with id that does not contain spaces. You can also do ROW_NUMBER() OVER(ORDER BY xxxxx) if you don't have such a thing.

You can probably make this a little harder to use indexes.

Answer 3

One good algorithm is to make comparisons outside and out when you get what you need. Since your target sequence requires a comparison between the first and last, the problem is fairly easy to implement. Shortening the sequence from the outside ensures that you get the largest sequence you need faster.

In your case, {1,6,3,5,2,8}

 1. Compare 1 and 8 2. Compare 1 and 2 3. Compare 6 and 8 4. Compare 6 and 2 and you got your sequence