增加递减序列

元素值首先减少然后增加的序列称为V序列。在一个有效的V-Sequence中，递减中应该至少有一个元素，并且至少有一个元素。例如，“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）中可以这样做吗？

来源

2012-03-20 simplest_coder

子序列的数目是相同的顺序，因为它们是按照原来的顺序，但不一定是连续的，对不对？ – gcbenison 2012-03-20 12:39:12

是的。它意味着你可以从原始序列中删除元素，但不能添加，并且删除的数量应该是最小的。 – 2012-03-20 13:44:25

http://stackoverflow.com/questions/9764512/longest-subsequence-that-first-increases-then-decreases/9764580#9764580 – 2012-03-22 03:37:06

该解决方案非常类似于最长非递减子序列的解决方案。不同之处在于，现在对于每个元素，您需要存储两个值 - 从该元素开始的最长V序列的长度是多少，以及从这个开始的最长的减少子序列的长度是多少。请看看typical non-decreasing subsequence解决方案的解决方案，我相信这应该是一个不错的提示。我相信你能达到的最好的复杂性是O（n * log（n）），但复杂度O（n^2）的解决方案更容易实现。

希望这会有所帮助。

来源

2012-03-20 09:29:51

这是一个基于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]

来源

2012-03-23 22:06:33 gcbenison

增加递减序列

回答

相关问题