递增递减序列

Question

一个元素的值先减后增的序列称为V-序列。在一个有效的V-序列中，至少应该有一个元素在减少阶段，至少有一个元素在增长阶段。

例如，“5 3 1 9 17 23”是一个有效的V-序列，其中有两个元素在减少阶段，即5和3，在增长阶段有3个元素，即9、17和23。但是，“6 4 2”或“8 10 15”序列都不是V-序列，因为“6 4 2”没有在增长部分中出现任何元素，而“8 10 15”没有在减少部分中出现任何元素。

给定一个包含N个数字的序列，请找到它的最长（不一定是连续的）子序列，它是一个V-序列？

是否可能在O(n)/O(logn)/O(n^2)时间内完成此操作？

- simplest_coder

---

子序列中的数字顺序与原序列相同，但不一定是连续的，对吗？ - gcbenison

是的，确切地说。这意味着您可以从原始序列中删除元素，但不能添加，并且删除的数量应尽量少。 - simplest_coder

重复的 https://dev59.com/RmHVa4cB1Zd3GeqPpLDB#9764580 - Sabbir Yousuf Sanny

@SabbirYousufSanny，你知道这个问题的解决方案吗？我的意思是O(nlog(n))的解决方案？ - simplest_coder

Answer 1

这个解决方案与最长非降子序列的解决方案非常相似。不同之处在于，现在对于每个元素，您需要存储两个值 - 从该元素开始的最长V序列的长度以及从此开始的最长递减子序列的长度。请查看典型非降子序列的解决方案，我相信这应该是一个足够好的提示。我认为您可以实现的最佳复杂度是O（n * log（n）），但是O（n ^ 2）复杂度的解决方案更容易实现。

希望这可以帮助到您。

- Ivaylo Strandjev

Answer 2

这里是基于izomorphius上面非常有帮助的提示的Python实现。它建立在增长子序列问题的此实现之上。正如izomorphius所说，它通过跟踪“到目前为止找到的最佳V”以及“到目前为止找到的最佳递增序列”来工作。请注意，一旦确定了V，将其扩展与扩展递减序列没有区别。此外，必须有一个规则从先前找到的递增子序列中“生成”新的候选V。

from bisect import bisect_left

def Vsequence(seq):
    """Returns the longest (non-contiguous) subsequence of seq that
    first increases, then decreases (i.e. a "V sequence").

    """
    # head[j] = index in 'seq' of the final member of the best increasing
    # subsequence of length 'j + 1' yet found
    head = [0]
    # head_v[j] = index in 'seq' of the final member of the best
    # V-subsequence yet found
    head_v = []
    # predecessor[j] = linked list of indices of best increasing subsequence
    # ending at seq[j], in reverse order
    predecessor = [-1] * len(seq)
    # similarly, for the best V-subsequence
    predecessor_v = [-1] * len(seq)
    for i in xrange(1, len(seq)):

        ## First: extend existing V's via decreasing sequence algorithm.
        ## Note heads of candidate V's are stored in head_v and that
        ## seq[head_v[]] is a non-increasing sequence
        j = -1  ## "length of best new V formed by modification, -1"
        if len(head_v) > 0:
            j = bisect_left([-seq[head_v[idx]] for idx in xrange(len(head_v))], -seq[i])

            if j == len(head_v):
                head_v.append(i)
            if seq[i] > seq[head_v[j]]:
                head_v[j] = i

        ## Second: detect "new V's" if the next point is lower than the head of the
        ## current best increasing sequence.
        k = -1  ## "length of best new V formed by spawning, -1"
        if len(head) > 1 and seq[i] < seq[head[-1]]:
            k = len(head)

            extend_with(head_v, i, k + 1)

            for idx in range(k,-1,-1):
                if seq[head_v[idx]] > seq[i]: break
                head_v[idx] = i

        ## trace new predecessor path, if found
        if k > j:
            ## It's better to build from an increasing sequence
            predecessor_v[i] = head[-1]
            trace_idx = predecessor_v[i]
            while trace_idx > -1:
                predecessor_v[trace_idx] = predecessor[trace_idx]
                trace_idx=predecessor_v[trace_idx]
        elif j > 0:
            ## It's better to extend an existing V
            predecessor_v[i] = head_v[j - 1]

        ## Find j such that:  seq[head[j - 1]] < seq[i] <= seq[head[j]]
        ## seq[head[j]] is increasing, so use binary search.
        j = bisect_left([seq[head[idx]] for idx in xrange(len(head))], seq[i])

        if j == len(head):
            head.append(i)  ## no way to turn any increasing seq into a V!
        if seq[i] < seq[head[j]]:
            head[j] = i

        if j > 0: predecessor[i] = head[j - 1]

    ## trace subsequence back to output
    result = []
    trace_idx = head_v[-1]
    while (trace_idx >= 0):
        result.append(seq[trace_idx])
        trace_idx = predecessor_v[trace_idx]

    return result[::-1]

一些示例输出：

>>> l1
[26, 92, 36, 61, 91, 93, 98, 58, 75, 48, 8, 10, 58, 7, 95]
>>> Vsequence(l1)
[26, 36, 61, 91, 93, 98, 75, 48, 10, 7]
>>> 
>>> l2
[20, 66, 53, 4, 52, 30, 21, 67, 16, 48, 99, 90, 30, 85, 34, 60, 15, 30, 61, 4]
>>> Vsequence(l2)
[4, 16, 48, 99, 90, 85, 60, 30, 4]

- gcbenison