subsecuencia más largo que el primero aumenta y luego disminuye

Question

estoy tratando de resolver la siguiente pregunta: ¿

---

Una secuencia en la que el valor de los elementos primero y luego aumentar disminución se llama V-secuencia. En una V-Sequence válida, debe haber al menos un elemento en el elemento decreciente y al menos uno en el brazo creciente.

Por ejemplo, "5 3 1 9 17 23" es una secuencia V válida que tiene dos elementos en el brazo decreciente, a saber, 5 y 3, y 3 elementos en el brazo creciente, es decir, 9, 17 y 23. Pero ninguna de las secuencias "6 4 2" o "8 10 15" son V-Sequence ya que "6 4 2" no tiene ningún elemento en la parte creciente, mientras que "8 10 15" no tiene ningún elemento en la parte decreciente.

Se obtiene una subsecuencia de una secuencia eliminando cero o más elementos de la secuencia. Por ejemplo, la definición "7", "2 10", "8 2 7 6", "8 2 7 10 6", etc. son subsecuencias válidas de "8 2 7 10 6"

Dada una secuencia de N números encuentra su subsecuencia más larga que es una secuencia en V

---

Actualmente tengo una solución en la que I primero inicializar una matriz (m []) de modo que cada m [i] contiene las secuencias crecientes más largos a partir de 'i' dentro de la matriz O (n^2).

De manera similar, inicializo otra matriz (d []), de modo que cada d [i] contiene la secuencia decreciente más larga QUE TERMINA en ese punto.

Ambas operaciones toman O (n^2)

ahora voy a través de estas matrices y elegir el valor máximo de m [i] + d [i] -1, de manera que las condiciones requeridas son satisfechos.

Lo que quiero saber es: ¿Hay una solución O (n lg n)? Porque mi solución no se ejecuta dentro de los límites de tiempo requeridos. Gracias :)

CÓDIGO:

#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

Hay O(NlgK) algoritmo para larga creciente problema Subsequence, donde K es la longitud LIS. Puede consultar Wikipedia para obtener una descripción del algoritmo. LightOJ también tiene un buen tutorial (esto podría requerir inicio de sesión).

Answer 2

Editar: Oh, esta respuesta es incorrecta. Me perdí la parte sobre poder eliminar elementos para hacer secuencias más largas. Sin embargo, para el entretenimiento, he aquí una solución para el caso sencillo en el que no se llega a eliminar elementos:

puedo pensar en una solución de O (n):

Camina la lista una vez.Mantener algunas variables:

• inicio de más larga v-secuencia visto
• longitud de más larga v-secuencia visto
• inicio de la corriente v-secuencia
• posición de escaneo actual
• estado de exploración actual (ascendente o descendente)

Inicialice ambos punteros de inicio en el primer elemento, el más largo en cero y el estado de exploración en descendente.

1. Camina por la lista siempre que los números sean descendentes y en descenso.
2. Cuando se encuentra un número creciente, cambie al estado ascendente y siga caminando
3. Cuando se encuentre el siguiente número decreciente, este es el final de una secuencia v.
4. Comparar con la secuencia v más larga actualmente encontrada y actualizarla si esta es más larga.
5. Restablecer inicio del actual V-secuencia y el estado de exploración a descendente
6. Camina la siguiente secuencia de
7. Al final de la matriz, inicio y duración de la secuencia más larga regresar.

Answer 3

Esta es una solución de O (n). Lo comprobó en ejemplos básicos.
Avíseme si tiene algún problema o si no funciona para ningún caso en particular.

CÓDIGO:

#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

array Construct inc [i] donde inc [i] tiendas más larga aumento subsecuencia terminando con A [i]. Construir matriz dec [i] donde dec [i] almacena la subsecuencia de disminución más larga que termina con A [i].

luego encontrar el valor máximo de (inc [i] + diciembre [i] - 1)