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

Последовательность, в которой значение элементов сначала уменьшается, а затем увеличивается, называется 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)?


algorithm dynamic-programming sequences
person simplest_coder    schedule 20.03.2012    source источник
comment
Числа в подпоследовательности расположены в том же порядке, что и в исходной последовательности, но не обязательно должны быть смежными, верно?   -  person gcbenison    schedule 20.03.2012
comment
да точно. Это означает, что вы можете удалять элементы из исходной последовательности, но не можете добавлять, и количество удалений должно быть минимальным.   -  person simplest_coder    schedule 20.03.2012
comment
Дубликат stackoverflow .com/questions/9764512/   -  person Sabbir Yousuf Sanny    schedule 22.03.2012
comment
@SabbirYousufSanny Знаете ли вы решение этой проблемы? Я имею в виду решение O (nlog (n))?   -  person simplest_coder    schedule 23.03.2012

Ответы (2)


arrow_upward
4
arrow_downward

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

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

person Ivaylo Strandjev    schedule 20.03.2012

arrow_upward
0
arrow_downward

Вот реализация на 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]
person gcbenison    schedule 23.03.2012