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

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, начиная с этого элемента, и какова длина самой длинной уменьшающейся подпоследовательности, начиная с этого. Пожалуйста, взгляните на решение решения typical non-decreasing subsequence, и я считаю, что это должно быть достаточно хорошим наконечником. Я считаю, что наилучшей сложности, которую вы можете достичь, является O (n * log (n)), но решение сложности O (n^2) легче достичь.

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

Answer 2

Вот реализация в Python на основе очень полезного намека izomorphius. Это строится на this implementation возрастающей проблемы с подпоследовательностями. Он работает, как говорит 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]