Massima sottosequenza crescente con programmazione dinamica

[antony881]

Il problema è il seguente :
Data una sequenza L di n numeri interi non necessariamente distinti , si scriva un algoritmo che calcoli la sottosequenza crescente di L di lunghezza massima :

L'equazione di ricorrenza che ho sviluppato è questa:

faccio partire l'indice da 0
Se j=n opt(j)=0, (caso base)
altrimenti opt(j)= max j
secondo voi è giusto fare cosi? la soluzione standard usata per questo tipico problema è quello di calcolare prima la massima sottosequenza crescente che termina in Li per tutti gli elementi della sequenza e poi si fa un massimo su questi valori cioè :

se i=1 opt(i)=1
altrimenti opt(i)=max 1<=j<=i-1 e Lj <= Li {opt(i)} +1 e poi fare il max su questi elementi.

quindi volevo sapere se secondo voi la mia soluzione era giusta ugualmente.

grazie a tutti.

[apatriarca]

Non mi è del tutto chiara la tua notazione ma se la differenza è solo quella di partire dalla fine invece che dall'inizio della successione allora è ugualmente corretto.

[hamming_burst]

Ciao,
questo problema era stato isolto con programmazione dinamica anni addietro.
In questo post:

https://www.matematicamente.it/forum/sot ... 11769.html

forse trovi già una risposta.

[antony881]

@ ham_burst : la soluzione che c è in quel post l'ho anche riscritta alla fine del mio post, il mio problema non è come risolverlo , me sa mia soluzione è ugualmente giusta.


per quanta riguarda la notazione opt(i) sta ad indicare il valore della soluzione ottima sulla sottosequenza 1...i