rosnąca sekwencja malejąca

Question

Sekwencja, w której wartość pierwiastków najpierw maleje, a następnie wzrasta, nazywa się V- Sequence. W prawidłowej Sekwencji V powinien znajdować się co najmniej jeden element w malejącym i co najmniej jednym elemencie w ramieniu podnoszącym.

Na przykład "5 3 1 9 17 23" jest prawidłową sekwencją V posiadającą dwa elementy w malejącym ramieniu, mianowicie 5 i 3, oraz 3 elementy w ramieniu podnoszącym, mianowicie 9, 17 i 23. Ale żadna z sekwencji "6 4 2" ani "8 10 15" nie jest sekwencją V, ponieważ "6 4 2" nie ma elementu w części zwiększającej się, podczas gdy "8 ​​10 15" nie ma elementu w malejącej części.

Biorąc pod uwagę, że sekwencja liczb N znajduje się najdłuższa (niekoniecznie ciągła) pod-sekwencja, która jest sekwencją V?

Czy można to zrobić w O (n)/O (logn)/O (n^2)?

Answer 1

Rozwiązanie jest dość podobne do rozwiązania najdłuższego nieodstępującego podciągu. Różnica polega na tym, że teraz dla każdego elementu należy zapisać dwie wartości - jaka jest długość najdłuższej sekwencji V rozpoczynającej się od tego elementu i jaka jest długość najdłuższego podciągu od tego początku. Proszę spojrzeć na rozwiązanie typical non-decreasing subsequence i uważam, że powinno to być wystarczająco dobrą wskazówką. Wierzę, że najlepszą złożonością, jaką możesz osiągnąć, jest O (n * log (n)), ale rozwiązanie złożoności O (n^2) jest łatwiejsze do osiągnięcia.

Mam nadzieję, że to pomoże.

Answer 2

Oto implementacja w Pythonie oparta na bardzo przydatnej podpowiedzi izomorphiusa powyżej. To buduje na this implementation problemu rosnącego podciągu. Działa, jak mówi izomorphius, śledząc "najlepsze znalezione dotąd V", a także "najlepiej rozwijające się sekwencje znalezione do tej pory". Zauważ, że rozszerzenie V, gdy zostanie zidentyfikowane, nie różni się od przedłużania sekwencji malejącej. Również musi istnieć reguła "odrodzenia" nowych kandydatów V z wcześniej znalezionych podciągających się podciągów.

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] 

Niektóre przykład wyjście:

>>> 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]