감소 시퀀스가 ​​증가합니다.

Question

요소 값이 처음으로 감소한 다음 증가하는 시퀀스를 V- 시퀀스라고합니다. 유효한 V-Sequence에는 감소하는 부분에는 적어도 하나의 요소가 있어야하고 증가하는 부분에는 적어도 하나의 요소가 있어야합니다.

예를 들어, "5 3 1 9 17 23"은 감소하는 팔에 2 개의 요소, 즉 5와 3을 갖는 유효한 V-Sequence이고 증가하는 부분에는 3 개의 요소, 즉 9, 17 및 23입니다. 그러나 "6 4 2 2"는 증가 부분에는 요소가없고 "8 10 15"에는 감소 부분에 요소가 없으므로 시퀀스 "6 4 2"또는 "8 10 15"중 하나도 V-Sequence가 아닙니다.

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

위의 izomorphius의 유용한 힌트를 기반으로 한 Python 구현입니다. 이것은 서브 시퀀스 문제가 증가하는 this implementation을 바탕으로합니다. izomorphius가 말했듯이 "지금까지 발견 된 최고의 V"뿐만 아니라 "지금까지 발견 된 최고의 서열"을 추적하여 작동합니다. 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]