crescente sequenza decrescente

Question

Una sequenza in cui il valore degli elementi prima diminuisce e quindi aumenta si chiama V- Sequenza. In una sequenza V valida, dovrebbe esserci almeno un elemento nel diminuire e almeno un elemento nel braccio crescente.

Ad esempio, "5 3 1 9 17 23" è una sequenza V valida avente due elementi nel braccio decrescente cioè 5 e 3 e 3 elementi nel braccio crescente cioè 9, 17 e 23. Ma nessuna delle sequenze "6 4 2" o "8 10 15" è V-Sequence poiché "6 4 2" non ha alcun elemento nella parte crescente mentre "8 10 15" non ha alcun elemento nella parte decrescente.

Data una sequenza di numeri N, trova la sua sottoregione più lunga (non necessariamente contigua) che è una sequenza-V?

E 'possibile farlo in O (n)/O (logn)/O (n^2)?

Answer 1

La soluzione è abbastanza simile alla soluzione della sottosequenza più lunga non decrescente. La differenza è che ora per ogni elemento è necessario memorizzare due valori: qual è la lunghezza della sequenza V più lunga che inizia da questo elemento e qual è la lunghezza della sottosequenza decrescente più lunga che inizia da questo. Si prega di dare un'occhiata alla soluzione della soluzione typical non-decreasing subsequence e credo che questo dovrebbe essere un suggerimento abbastanza buono. Credo che la migliore complessità possibile sia O (n * log (n)), ma una soluzione di complessità O (n^2) è più facile da ottenere.

Spero che questo aiuti.

Answer 2

Ecco un'implementazione in Python basata sul suggerimento molto utile di izomorpio sopra. Questo si basa su this implementation del crescente problema di sottosuccessione. Funziona, come dice izomorphius, tenendo traccia di "i migliori V trovati finora" e delle "sequenze sempre migliori trovate finora". Si noti che estendere una V, una volta identificata, non è diversa dall'estensione di una sequenza decrescente. Inoltre deve esserci una regola per "generare" nuovi candidati V da sottosezioni crescenti precedentemente rilevate.

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] 

Qualche esempio di uscita:

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