più lunga sottosequenza che prima aumenta poi diminuisce

Question

sto cercando di risolvere il seguente problema:

---

Una sequenza in cui è chiamato il valore di primi elementi di flessione e quindi aumentare V- Sequence. 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.

Una sottocategoria di una sequenza viene ottenuta eliminando zero o più elementi dalla sequenza. Ad esempio, definizione "7", "2 10", "8 2 7 6", "8 2 7 10 6" ecc. Sono sotto-sequenze valide di "8 2 7 10 6"

Data una sequenza di numeri N trova la sua sotto-sequenza più lunga che è una sequenza-V.

---

Attualmente ho una soluzione in cui ho inizializzare un array (m []) in modo tale che ciascun m [i] contiene le sequenze crescenti più lunghi a partire da 'i' all'interno della matrice O (n^2).

Analogamente, inizializzo un altro array (d []), in modo tale che ogni d [i] contenga la sequenza decrescente più lunga ENDING in quel punto.

Entrambe queste operazioni richiedono O (n^2)

ora passare attraverso queste matrici e selezionare il valore massimo di m [i] + d [i] -1, in modo tale che le condizioni richieste sono soddisfatte.

Quello che voglio sapere è - C'è una soluzione O (n lg n) ?? Perché la mia soluzione non viene eseguita entro i limiti di tempo richiesti. Grazie :)

CODICE:

#include<cstdio> 
#include<algorithm> 

using namespace std; 



int m[ 200000 ]; 
int d[200000 ]; 
int n; 
int arr[200000 ]; 

void LIS() 
{ 
    m[ n-1 ] = 1; 

    int maxvPos = -1; 
    int maxv = -1; 

    for(int i=n-2; i>=0; i--) 
    { 
     maxv = -1; 
     for(int j=i+1; j<n; j++) 
     { 
      if((m[j]+1 > maxv) && (arr[i] < arr[j])) 
      { 
       maxv = m[j]+1; 
       maxvPos = j; 
      } 


     } 
     if(maxv>0) 
      { 
       m[i] = maxv; 
      } 

      else 
       m[i ] = 1; 
    } 

} 

void LDS() 
{ 
     d[0] = 1; 

    int maxv = -1; 
    int maxvPos = -1; 

    for(int i=1; i<n; i++) 
    { 
     maxv = -1; 
     for(int j=i-1; j>=0; j--) 
     { 
      if((d[j]+1 > maxv) && arr[j]>arr[i]) 
      { 
       maxv = d[j]+1; 
       maxvPos = j; 
      } 
     } 

     if(maxv>0) 
      d[i] = maxv; 

     else 
      d[i]=1; 
    } 

} 

int solve() 
{ 
    LIS(); 
    LDS(); 

    int maxv = 0; 
    int curr = 0; 

    for(int i=0; i<n; i++) 
    { 
     curr = d[i] + m[i] -1 ; 

     if((d[i]>0) && (m[i]>0)) 
     { 
      if(curr != 1) 
      maxv = max(curr, maxv); 
     } 

    } 

    return maxv; 

} 

/* static void printArr(int[] a) 
{ 
    for(int i : a) 
     System.out.print(i + " "); 

    System.out.println(); 
} */ 


int main() 
{ 
    scanf("%d", &n); 

    for(int i=0; i<n; i++) 
    { 
     scanf("%d", &arr[i]); 
    } 

    printf("%d\n", solve()); 
    return 0; 

} 

Answer 1

Ci sono O(NlgK) algoritmo per Longest crescente problema Subsequence, dove K è la lunghezza LIS. È possibile controllare Wikipedia per una descrizione dell'algoritmo. LightOJ ha anche un bel tutorial (questo potrebbe richiedere il login).

Answer 2

Modifica: Oh, questa risposta è sbagliata. Ho perso la parte relativa alla possibilità di eliminare elementi per creare sequenze più uniformi. Eppure, per l'intrattenimento, ecco una soluzione per il semplice caso in cui non si ottiene per eliminare elementi:

mi viene in mente una soluzione O (n):

Walk the lista una volta.Mantenere alcune variabili:

• inizio della più lunga v-sequenza visto
• lunghezza più lunga v-sequenza visto
• inizio della corrente v-sequenza
• posizione di scansione corrente
• stato attuale scansione (ascendente o decrescente)

Inizializza entrambi i puntatori iniziali sul primo elemento, il più lungo a zero e lo stato di scansione su discendente.

1. Percorrere l'elenco finché i numeri sono discendenti e in stato discendente.
2. Quando si incontra un numero crescente, passare allo stato crescente e continuare a camminare
3. Quando il successivo numero decrescente viene encouterato, questa è la fine di una sequenza v.
4. Confronta con la sequenza v più recente attualmente rilevata e aggiorna quella se questa è più lunga.
5. reset inizio della corrente v-sequenza e lo stato di scansione a discendente
6. Walk the sequenza successiva
7. Alla fine della matrice, iniziale e la lunghezza della sequenza più lunga ritorno.

Answer 3

Questa è una soluzione O (n). Controllato su esempi di base.
Fammi sapere se ha qualche problema o se non funziona per un caso particolare.

CODICE:

#include<stdio.h> 
int max(int a,int b) 
{ 
return (a >= b ? a : b); 
} 
int main() 
{ 
    int i,j,n; 
    scanf("%d",&n); 
    int A[200022]; 
    int dec[200022]={0}; 
    int V[200022]={0}; 
    int state[200022]={0}; 
    for(i=0;i<n;i++) 
    { 
     scanf("%d",&A[i]); 
    } 
    if(A[0] > A[1]) 
     state[0]=1; 
    for(i=1;i<n;i++) 
    { 
     j=i-1; 
      if(A[i] < A[j]) 
      {  
       dec[i]=max(dec[i],dec[j]+1); 
       V[i]=max(V[i],V[j]); 
       state[i]=1; 
      }  
      else if(A[i] == A[j]) 
      {  
       dec[i]=dec[j]; 
       V[i]=V[j]; 
       state[i]=state[j]; 
      } 
      else 
      { 
       if(state[j]==1) 
       { 
        dec[i]=dec[i]; 
        V[i]=max(V[i],dec[j]+1); 
        V[i]=max(V[i],V[j]+1); 
        state[i]=1; 
       } 
       else 
       { 
        dec[i]=dec[i]; 
        V[i]=max(V[i],V[j]); 
       } 
      } 

// printf("%d %d\n",dec[i],V[i]); 
} 
    if(V[n-1] == 0) 
     printf("0\n"); 
    else 
     printf("%d\n",V[n-1]+1); 
} 

Answer 4

Costrutto matrice inc [i], dove inc [i] esercizi Maggiore crescente sottosequenza termina con A [i]. Costruisci array dec [i] dove dec [i] memorizza la sottosequenza Decrescente più lunga che termina con A [i].

quindi trovare il valore massimo di (inc [i] + dicembre [i] - 1)