возрастающая убывающая последовательность

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)?

Answer 1

Решение очень похоже на решение самой длинной неубывающей подпоследовательности. Разница в том, что теперь для каждого элемента вам нужно хранить два значения - какова длина самой длинной V-последовательности, начиная с этого элемента, и какова длина самой длинной убывающей подпоследовательности, начинающейся с этого. Пожалуйста, взгляните на решение типичного решения неубывающей подпоследовательности , и я считаю, что этот совет должен быть достаточно хорошим. Я считаю, что лучшая сложность, которую вы можете достичь, - это O (n * log (n)), но решение сложности O (n ^ 2) легче достичь.

Надеюсь, это поможет.

Answer 2

Вот реализация в 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]