c# - 给定一个序列，找到最大的 'reverse-ordered' 子序列

Question

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

[修订:如答案部分所述，后续不是正确的描述。 一对数字是正确的词!]

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

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

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

谢谢。

Answer 1

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

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