più lunga sottosequenza convessa in un array

Question

Supponiamo di avere una matrice di input di interi, come trovare sottosequenza convesso lungo che soddisfa la seguente condizione:

c[i] < (c[i-1] + c[i+1])/2 

c[i-1], c[i] e c[i+1] sono tre elementi consecutivi nel sotto sequenza.

Ad esempio, se l'array di input è { 1, 2, -1, 0, 3, 8, 5 }, la sottosequenza convessa più lunga deve essere: { 1, -1, 0, 3, 8 } o { 2, -1, 0, 3, 8 }.

Ho cercato di risolvere questo problema utilizzando la stessa idea di programmazione dinamica nel problema "Lest (Aumento crescente)". Ma poiché ogni elemento nella sottosequenza dipende dai due elementi precedenti, sembra che una soluzione O (n^2) sia impossibile. Grazie per l'aiuto.

Answer 1

Ecco O (N log N) algoritmo (e dal log N è qui solo perché di smistamento potremmo ridurre questo a O (N log log N) o addirittura a O (N ) con differenti algoritmi di ordinamento o più code di priorità advanced):

1. creare un array per ciascuna coppia di elementi di campo in ingresso: P[]. Gli elementi all'interno di ciascuna coppia sono ordinati in base all'indice.
2. Ordinare queste coppie in base alla differenza di valore Y2 - Y1. In caso di uguali valori Y2 - Y1, dovrebbero essere ordinati per secondo indice in ordine decrescente.
3. Zero-initialize array L[] delle lunghezze di sottosequenza per le sottosequenze che terminano con gli indici 0 .. N-1.
4. Per ogni coppia da P[] (in ordine): L[X2] = max(L[X2], L[X1] + 1). Dove X è l'indice dell'elemento nell'array di input.
5. Trova il valore più grande in L[]. Questa è la lunghezza della sottosequenza convessa più lunga.
6. Per poter ricostruire la sottosequenza stessa, il passaggio 4 deve anche aggiornare la catena dei puntatori. Quando viene aggiornato L[X2], verrà creato un nodo che punta al nodo indicato per la voce corrispondente a X1, quindi la voce corrispondente a X2 a questo nuovo nodo: BP_Head[X2] = new Node(BP_Head[X1]).

convesso proprietà c[i] < (c[i-1] + c[i+1])/2 può essere trasformata in diseguaglianza equivalente c[i] - c[i-1] < c[i+1] - c[i]. Il che significa che durante l'elaborazione delle coppie nell'ordine ordinato non è più necessario controllare la proprietà convessa. Quindi l'unico compito del punto # 4 è quello di far crescere le sottostringhe.

Questa variante semplificata dell'algoritmo ha bisogno dello spazio O (N). La complessità dello spazio può essere ridotta se invece di un grande array P[] usiamo una copia pre-ordinata dell'array di input S[] insieme alla coda di priorità. Il passo 4 riceve gli elementi dall'alto di questa coda di priorità. Per mantenere la dimensione di questa coda di priorità uguale a N, è possibile spingere l'elemento S[i+1] - S[j] nella coda solo dopo che è stato rimosso S[i] - S[j] (quindi la coda mantiene solo un elemento per ogni j).Lo spazio enorme consumato dalla foresta di backpointers non è necessario se usiamo un trucco DP noto per archiviare solo un back-pointer (per ogni indice) che punta a "middle" della catena back-pointer originale (e quindi ripetere questo algoritmo ricorsivamente per due sotto-array che precedono e seguono questo "back-pointer" centrale).

---

e O (N) algoritmo:

1. grafico Costrutto dove ogni vertice corrisponde (in ordine di indice) coppia di elementi dell'array.
2. Collegare i vertici con uno spigolo se hanno un elemento di matrice comune che si trova tra i rimanenti due elementi associati a questi vertici e tutti e tre gli elementi soddisfano la proprietà convessa. Questo bordo dovrebbe essere diretto al vertice con indici più grandi.
3. Aggiungere i nodi di origine e destinazione e collegarli a tutti i vertici.
4. Trova il percorso più lungo in questo grafico.

Questo grafico è O (N 2 ) vertici e O (N) bordi. Può essere costruito in tempo O (N); e poiché si tratta di un DAG, la ricerca del percorso più lungo richiede anche il tempo O (N).

Answer 2

Consente di chiamare la sequenza convessa più lunga come LCS; La lunghezza minima possibile per N> 1 è 2. L'algo sotto è auto esplicativo.

int LCS[N]; 
LCS[0] = 1; LCS[1] =2 ; 

for(i=2;i<N;i++) 
{ 
    LCS[i] = 2; 
    for(j=1;j<i;j++) 
    { 
     for(k=0;k<j;k++) 
     { 
      if(LCS[j]-1 == LCS[k] && A[j] < (A[k] + A[i])/2) 
       LCS[i] = max(LCS[i], 1+LCS[j]); 
     } 
    } 
}