[ALGORITMO] Massima sottosequenza comune

[Cesaropa12]

Creare un algoritmo con tempoO (n lg n) per trovare la più luna sottosequenza monotonicamente crescente di un sequenza di n numeri.

[alka]

Anche se le tue domande riguardano algoritmi, questa informazione va comunque specificata nel linguaggio. La inserisco io...questa volta......

[fisica]

immagino che la sequenza di numeri non sia ordinata, se no la risposta è abbastanza banale...

cosa vuol dire "tempoO (n lg n) "??

al di là di questo ecco una proposta:

1: leggo il primo numero e lo metto in memoria
2: leggo il successivo
     2a: se è maggiore di quello in memoria torno al 2
     2b: se è minore di quello in memoria e non l'ho già scritto lo sostituisco in memoria
     2c: torno al punto 2
3: scrivo il valore in memoria
4: torno al punto 1

[Cesaropa12]

Per massima sottosequenza comune intendo la massima sottosequenza che si trova con la programmazione dinamica.
Ad esempio la massima sottosequenza di 3-5-10-2-14-3-20 è 3-5-10-14-20.
Comunque la soluzione l'ho trovata,i passi sono questi:
-ordinare l'array
-usare l'algoritmo della massima sottoseqeunza comune fra l'array iniziale e quello ordinato.