algorithm - mas - longest increasing subsequence

La subsecuencia creciente más larga(O(nlogn))

Question

LIS:wikipedia

Hay una cosa que no puedo entender:

¿Por qué es X [M [i]] una secuencia no decreciente?

Answer 1

Esta es la solución O (n * lg (n) de la Guía del autostopista para los concursos de programación (nota: esta implementación supone que no hay duplicados en la lista):

set<int> st;
set<int>::iterator it;
st.clear();
for(i=0; i<n; i++) {
  st.insert(array[i]);
  it=st.find(array[i]);
  it++;
  if(it!=st.end()) st.erase(it);
}
cout<<st.size()<<endl;

Para tener en cuenta los duplicados, se puede verificar, por ejemplo, si el número ya está en el conjunto. Si es así, ignore el número, de lo contrario continúe usando el mismo método que antes. Alternativamente, uno podría revertir el orden de las operaciones: primero elimine, luego inserte. El siguiente código implementa este comportamiento:

set<int> st;
set<int>::iterator it;
st.clear();
for(int i=0; i<n; i++) {
    it = st.lower_bound(a[i]);
    if (it != st.end()) st.erase(it);
    st.insert(a[i]);
}
cout<<st.size()<<endl;

El segundo algoritmo podría extenderse para encontrar la subsecuencia de mayor crecimiento (LIS) al mantener una matriz principal que contenga la posición del elemento anterior de la LIS en la matriz original.

typedef pair<int, int> IndexValue;

struct IndexValueCompare{
    inline bool operator() (const IndexValue &one, const IndexValue &another){
        return one.second < another.second;
    }
};

vector<int> LIS(const vector<int> &sequence){
    vector<int> parent(sequence.size());
    set<IndexValue, IndexValueCompare> s;
    for(int i = 0; i < sequence.size(); ++i){
        IndexValue iv(i, sequence[i]);
        if(i == 0){
            s.insert(iv);
            continue;
        }
        auto index = s.lower_bound(iv);
        if(index != s.end()){
            if(sequence[i] < sequence[index->first]){
                if(index != s.begin()) {
                    parent[i] = (--index)->first;
                    index++;
                }
                s.erase(index);
            }
        } else{
            parent[i] = s.rbegin()->first;
        }
        s.insert(iv);
    }
    vector<int> result(s.size());
    int index = s.rbegin()->first;
    for(auto iter = s.rbegin(); iter != s.rend(); index = parent[index], ++iter){
        result[distance(iter, s.rend()) - 1] = sequence[index];
    }
    return result;
}

Answer 2

La idea base detrás del algoritmo es mantener una lista de LIS de una longitud dada que termina con el elemento más pequeño posible. Construyendo tal secuencia

1. Encuentre el predecesor inmediato en la secuencia de los últimos elementos ya conocidos (digamos que es de longitud k )
2. Intente agregar el elemento actual a esta secuencia y crear una nueva solución mejor para k+1 longitud

Debido a que en el primer paso busca valores más pequeños, entonces X [i] la nueva solución (para k+1 ) tendrá el último elemento mayor que la secuencia más corta.

Espero que ayude

Answer 3

Necesitamos mantener listas de secuencias crecientes.

En general, hemos establecido listas activas de longitud variable. Estamos agregando un elemento A [i] a estas listas. Escaneamos las listas (para los elementos finales) en orden decreciente de su longitud. Verificaremos los elementos finales de todas las listas para encontrar una lista cuyo elemento final sea más pequeño que A [i] (valor mínimo).

Nuestra estrategia determinada por las siguientes condiciones,
1. Si A [i] es el más pequeño entre todos los candidatos finales de las listas activas, comenzaremos una nueva lista activa de longitud 1.
2. Si A [i] es el más grande entre todos los candidatos finales de las listas activas, clonaremos la lista activa más grande y la extenderemos por A [i].
3. Si A [i] está en el medio, encontraremos una lista con el elemento final más grande que sea más pequeño que A [i]. Clona y amplía esta lista con A [i]. Descartaremos todas las demás listas de la misma longitud que la de esta lista modificada.

Tenga en cuenta que en cualquier caso durante nuestra construcción de listas activas, se mantiene la siguiente condición.

“El elemento final de una lista más pequeña es más pequeño que los elementos finales de las listas más grandes”.

Quedará claro con un ejemplo, tomemos un ejemplo de wiki:
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.

A [0] = 0. Caso 1. No hay listas activas, cree una.
0.
-------------------------------------------------- ---------------------------
A [1] = 8. Caso 2. Clonar y extender.
0.
0, 8.
-------------------------------------------------- ---------------------------
A [2] = 4. Caso 3. Clone, extienda y descarte.
0.
0, 4.
0, 8. Desechado
-------------------------------------------------- ---------------------------
A [3] = 12. Caso 2. Clonar y extender.
0.
0, 4.
0, 4, 12.
-------------------------------------------------- ---------------------------
A [4] = 2. Caso 3. Clone, extienda y descarte.
0.
0, 2.
0, 4. Desechado.
0, 4, 12.
-------------------------------------------------- ---------------------------
A [5] = 10. Caso 3. Clone, extienda y deseche.
0.
0, 2.
0, 2, 10.
0, 4, 12. Se desecha.
-------------------------------------------------- ---------------------------
A [6] = 6. Caso 3. Clone, extienda y deseche.
0.
0, 2.
0, 2, 6.
0, 2, 10. Se desecha.
-------------------------------------------------- ---------------------------
A [7] = 14. Caso 2. Clonar y extender.
0.
0, 2.
0, 2, 6.
0, 2, 6, 14.
-------------------------------------------------- ---------------------------
A [8] = 1. Caso 3. Clonar, extender y descartar.
0.
0, 1.
0, 2. Desechado.
0, 2, 6.
0, 2, 6, 14.
-------------------------------------------------- ---------------------------
A [9] = 9. Caso 3. Clone, extienda y deseche.
0.
0, 1.
0, 2, 6.
0, 2, 6, 9.
0, 2, 6, 14. Desechado.
-------------------------------------------------- ---------------------------
A [10] = 5. Caso 3. Clone, extienda y deseche.
0.
0, 1.
0, 1, 5.
0, 2, 6. Se desecha.
0, 2, 6, 9.
-------------------------------------------------- ---------------------------
A [11] = 13. Caso 2. Clonar y extender.
0.
0, 1.
0, 1, 5.
0, 2, 6, 9.
0, 2, 6, 9, 13.
-------------------------------------------------- ---------------------------
A [12] = 3. Caso 3. Clone, extienda y descarte.
0.
0, 1.
0, 1, 3.
0, 1, 5. Desechado.
0, 2, 6, 9.
0, 2, 6, 9, 13.
-------------------------------------------------- ---------------------------
A [13] = 11. Caso 3. Clone, extienda y deseche.
0.
0, 1.
0, 1, 3.
0, 2, 6, 9.
0, 2, 6, 9, 11.
0, 2, 6, 9, 13. Desechado.
-------------------------------------------------- ---------------------------
A [14] = 7. Caso 3. Clone, extienda y descarte.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7. 0, 2, 6, 9. Se desecha.
0, 2, 6, 9, 11.
-------------------------------------------------- ----------------------------
A [15] = 15. Caso 2. Clonar y extender.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9, 11.
0, 2, 6, 9, 11, 15. <- Lista LIS

Además, asegúrese de que hemos mantenido la condición, "el elemento final de una lista más pequeña es más pequeño que los elementos finales de las listas más grandes".
Este algoritmo se llama clasificación de paciencia.
en.wikipedia.org/wiki/Patience_sorting

Por lo tanto, elige un traje de la baraja de cartas. Encuentra la subsecuencia de cartas cada vez más larga del palo barajado. Nunca olvidarás el enfoque.

Complejidad: O (NlogN)

Fuente: http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

Answer 4

Veamos primero el algoritmo n ^ 2:

dp[0] = 1;
for( int i = 1; i < len; i++ ) {
   dp[i] = 1;
   for( int j = 0; j < i; j++ ) {
      if( array[i] > array[j] ) {
         if( dp[i] < dp[j]+1 ) {
            dp[i] = dp[j]+1;
         }
      }
   }
}

Ahora la mejora ocurre en el segundo bucle, básicamente, puede mejorar la velocidad utilizando la búsqueda binaria. Además de la matriz dp [], tengamos otra matriz c [], c es bastante especial, c [i] significa: el valor mínimo del último elemento de la secuencia creciente más larga cuya longitud es i.

sz = 1;
c[1] = array[0]; /*at this point, the minimum value of the last element of the size 1 increasing sequence must be array[0]*/
dp[0] = 1;
for( int i = 1; i < len; i++ ) {
   if( array[i] < c[1] ) {
      c[1] = array[i]; /*you have to update the minimum value right now*/
      dp[i] = 1;
   }
   else if( array[i] > c[sz] ) {
      c[sz+1] = array[i];
      dp[i] = sz+1;
      sz++;
   }
   else {
      int k = binary_search( c, sz, array[i] ); /*you want to find k so that c[k-1]<array[i]<c[k]*/
      c[k] = array[i];
      dp[i] = k;
   }
}

Answer 5

se me ocurrió esto

set<int> my_set;
set<int>::iterator it;
vector <int> out;
out.clear();
my_set.clear();
for(int i = 1; i <= n; i++) {
    my_set.insert(a[i]);
    it = my_set.find(a[i]);
    it++;
    if(it != my_set.end()) 
        st.erase(it);
    else
        out.push_back(*it);
}
cout<< out.size();