Sottosequenza monotonicamente crescente

[Cesaropa12]

Cormen.Es15.4-5. Creare un algoritmo con tempo O(n alla seconda) per trovare la più lunga sottosequenza monotonicamente crescente di una sequenza di n numeri.

[vl4dster]

assumo che la sequenza di numeri e' in un array... ma l'idea dovrebbe funzionare con poche modifiche anche per le liste...
questo dovrebbe essere $O(n)$ e quindi anche $O(n^2)$, non capisco perche' si chieda proprio $O(n^2)$ comunque...
l'idea e': tengo due indici interi, left right, che all'inizio indicizzano il primo elemento dell'array. Poi incremento right fino a che non trovo:

array
 < array[right -1]

a questo punto ho trovato una sottosequenza monotona: memorizzo la sua lunghezza e memorizzo la sua posizione con old_left, old_right. Poi aggiorno left e inizio a cercare la prossima sequenza, se e' piu' lunga della vecchia la memorizzo, altrimenti no.

E' molto piu' difficile a dirsi, quindi:
(in pseudo codice considero i valori dell'array da 1 a length[array] (e non da 0 a length[array]-1))

cerca(array[]){
   old_left = 1;
   old_right = 2;   
   left = 1;
   right = 2;

   for(right; right <= length[array]; right++){
       if(array
 < array[right-1] &&
          ((right -1) - left +1) > (old_right - old_left +1)){
          old_left = left;
          old_right = right-1;
          left = right;
       }
   }

   stampa_array(array[], old_left, old_right);
}

nota: se trova due sottosequenze piu' lunghe stampa la prima

ammesso che compilato funzioni, non vorrei fare l'antipatico pero', anche per informatica, quando posti un esercizio sarebbe bene che tu provassi a farlo o almeno a proporre un'idea per la soluzione

EDIT: mannaggia! ho capito perche' lo vuoi O(n^2), per sottosequenza intendi le sottosequenze definite nella programmazione dinamica! Beh, non l'ho ancora studiata

[Cesaropa12]

""mannaggia! ho capito perche' lo vuoi O(n^2), per sottosequenza intendi le sottosequenze definite nella programmazione dinamica! Beh, non l'ho ancora studiata ""
Ho capito che hai inteso male l'esercizio.Beh...diciamo che se per sottosequenza intendi una sequenza di numeri vicini è molto semplice il problema ed avevi quindi motivo di dirmi di provare a risolvere il problema. Ma il punto è che si tratta di un esercizio di programmazione dinamica. Qualcuno ha pensato ad una soluzione?

[vl4dster]

Per la serie meglio tardi che mai, ho ritrovato per caso il topic, ed ecco la mia solution (anche perche' tra poco ho l'esame di algo2 ):

Sia $X = $ la sequenza

Sia $c$ la lunghezza della piu' lunga sottosequenza crescente di $X_i = $
Non sto a fare la dimostrazioncina della sottostruttura ottima dei sottoproblemi che tanto e' banale.

Assumiamo per comodita' $max\emptyset = 0$
Si puo' notare che:
$c = 1" se "i = 1$
$c = 1 + max{c[j] : 1<=j1$

Il valore ottimo sara' dato da $f^* = max{c:1<=i<=|X|}$

A questo punto si puo' scrivere l'algo bottom-up che calcola lunghezza e sequenza (in pseudo-codice):

SOTTOSEQ-MONOTONA(X){
  c[1] = 1
  for i=2 to |X|{
     conta = 0      //cerco la prossima seq massima
     pos = 1
     for j = 1 to i-1{ //ricordiamo che a questo punto la lunghezza da 1 a i-1 e' nota
         if (x_j <= x_i) && (x_j > conta){
             conta = c[j]
             pos = j
         }
      c[i] = 1+conta
      seq[i] = pos        //permette di ricostruire la sequenza
     }
  }
   return c
}

i due for portano una complessita' di $O(|X|^2)$ come richiesto.

allora la sequenza e' facilmente ricostruibile dall'array $c$ con il seguente algo:

STAMPA-SEQ(seq, posizione){
    STAMPA-SEQ(seq[posizione])
    PRINT(X_posizione)
}

Sperando di non aver commesso errori propongo la versione LCIS, la soluzione e' concettualmente simile:

Trovare un algo di prog dinamica di complessita' $O((|X||Y|)^2)$ per il problema:
INPUT: due sequenze $X$ e $Y$
OUTPUT: la piu' lunga sottosequenza monotona non descrescente _comune_ tra $X$ e $Y$