c# - 如何在 C# 中的列表中查找连续整数？

Question

如何从 C# 中的整数列表中找到整数的最长递增子序列？

Answer 1

您只需要分解成一个更小的问题，即在给定起点的情况下找到递增序列的长度。

在伪代码中，这类似于:

def getSeqLen (int array[], int pos):
    for i = pos + 1 to array.last_element:
         if array[i] <= array[i-1]:
             return i - pos
    return array.last_element + 1 - pos

然后遍历数组，查看这些单独的序列。您知道序列必须在特定点分开，否则序列会更长。换句话说，这些递增序列没有重叠:

def getLongestSeqLen (int array[]):
    pos = 0
    longlen = 0
    while pos <= array.last_element:
        len = getSeqLen (array, pos)
        if len > longlen:
            longlen = len
        pos = pos + len
    return longlen

通过图形解释的方式，考虑以下顺序:

 element#: 0  1  2  3  4  5  6  7  8  9 10 11 12
    value: 9 10 12  7  8  9  6  5  6  7  8  7  8
                  ^        ^  ^           ^     ^

在这种情况下，^ 字符标记了子序列的明确边界。

从元素 0 开始，getSeqLen 返回 3。由于这大于当前最长长度 0，我们保存它并将 3 添加到当前位置(得到 3)。

然后在元素 3 处，getSeqLen 返回 3。由于这不大于当前最长长度 3，我们忽略它但我们仍将 3 添加到当前位置(得到 6)。

然后在元素 6 处，getSeqLen 返回 1。由于这不大于当前最长长度 3，因此我们忽略它但我们仍将 1 加到当前位置(得到 7)。

然后在元素 7 处，getSeqLen 返回 4。由于这大于当前最长长度 3，我们保存它并将 4 加到当前位置(得到 11)。

然后在元素 11 处，getSeqLen 返回 2。由于这不大于当前最长长度 4，我们忽略它但我们仍将 2 添加到当前位置(得到 13)。

然后，由于元素 13 超出了末尾，我们简单地返回找到的最长长度 (4)。