4

（是的，我已经尽可能多地搜索了......）也许我不应该使用序列，但没有更好的方式来描述它......

[修订：如答案部分所述，子序列不是正确的描述。一对数字是正确的词！]

给定一个数字序列，并将序列中一对数字的大小定义为两个数字之间的距离。显然最大的一对是[第一个数字，最后一个数字]。问题是找到顺序与 [first,last] 对相反的最大数字对。

例如，如果序列是，{1,6,3,5,2,8}那么答案应该是 [6,2]因为 [1,8] 的顺序是递增的，而递减顺序的最大对是 [6,2]。

一个附带的问题是，这可以使用类似 SQL 的语句以声明性方式解决吗？具体来说，我正在考虑使用 LINQ 来做到这一点。

谢谢。

4

3 回答 3

0

这不是适合 SQL 的问题。它的措辞也很糟糕。您实际上是在寻找数字对而不是子序列，而大小是两者之间的距离。

可以通过向后扫描序列来求解O(n)，找出给定点之后的最小数字及其位置。这给出{1,2,2,2,2,8)和{0,4,4,4,4,5}。然后与原始序列并行扫描得到大小为{0,3,2,1,0,0}，因此最大大小为(6,2)大小为 3 的对。

于 2013-01-30T08:01:36.200 回答
0

未经测试，但我会尝试以下方法：

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

您也应该能够在 LINQ 中实现此解决方案，方法是计算从每个点到匹配数字的距离（从末尾开始）。

然而，在 SQL 中实现这一点会稍微困难一些，尽管你绝对可以做到。这是我的尝试和一个有效的 SQL Fiddle 示例：

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

id这假设您有一个不包含 gaps的升序标识列。ROW_NUMBER() OVER(ORDER BY xxxxx)如果您没有这样的事情，您也可以这样做。

为了使用索引，您可能会使其变得更复杂一些。

于 2013-01-30T08:05:50.567 回答
0

一个好的算法是从外向内进行比较，一旦你得到你需要的就中断。由于你的目标序列需要在第一个和最后一个之间进行比较，这个问题很容易实现。从外部缩小序列可确保您更快地获得所需的最大序列。

在您的情况下， {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
于 2013-01-30T08:27:36.823 回答