減少シーケンスが増加する

Question

要素の値が最初に減少して増加するシーケンスをVシーケンスと呼びます。有効なVシーケンスでは、減少する部分に少なくとも1つの要素があり、増加する部分に少なくとも1つの要素が存在する必要があります。

たとえば、「5 3 1 9 17 23」は、減少するアームの2つの要素、つまり5と3、および増加するアームの3つの要素、つまり9,17と23を持つ有効なVシーケンスです。しかし、「6 4 2 2」は増加部分に要素がなく、「8 10 15」は減少部分に要素がないので、シーケンス「6 4 2」または「8 10 15」のいずれもVシーケンスではない。

N個の数字のシーケンスがV-シーケンスである最長の（必ずしも連続している必要はない）サブシーケンスを見つけるとすれば、

これはO（n）/ O（logn）/ O（n^2）で可能ですか？

Answer 1

このソリューションは、最長非減少サブシーケンスのソリューションに非常に似ています。違いは、各要素の2つの値を格納する必要があることです。この要素から始まる最長Vシーケンスの長さと、これから始まる最長減少サブシーケンスの長さはどのくらいですか。 typical non-decreasing subsequenceソリューションのソリューションを見てください。これは十分なヒントになるはずです。私はあなたが達成できる最高の複雑さはO（n * log（n））だと信じていますが、複雑さO（n^2）の解を達成する方が簡単です。

これが役に立ちます。

Answer 2

izomorphiusに基づいたPythonの実装です。上のヒントを参考にしてください。これは、増加するサブシーケンス問題の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]