Algoritmi e Strutture dati & Programmazione dinamica

[alex170]

Ciao a tutti
Sto cercando di capirla, davvero, ma non mi riesce. Anzi, la capisco ma non riesco ad applicarla.
E questo vale tanto per la PD tanto per la Tecnica Greedy (o Tecnica Golosa, se preferite).
Ad esempio:

Sia dato un array $A$ di interi positivi e negativi. Un sottoarray è una sequenza di elementi che occupano posizioni consecutive in $A$. Un sottoarray è positivo se i suoi elementi sono positivi. Si vuole individuare il sottoarray positivo più lungo.

Qui un esempio dove in rigio è colorato il sottoarray più lungo
https://www.dropbox.com/s/ujgbzidfozozup7/IMG_20130703_151151.jpg

Indichiamo con $ s(i) $ la lunghezza del più lungo sottoarray positivo che termina in $A(i)$ con $1<=i<=n$
Si chiede di:

1- scrivere un'equazione ricorsiva per $s(i)$;
2 - scrivere un algoritmo basato sula PD che calcola $s(i)$ ricevendo in input l'array $A$;
3 - scrivere lo pseudo-codice di un algoritmo che stampa la soluzione ottima per il problema (cioè il più lungo sottoarray positivo di $A$);
4 - dire qual è la complessità degli algoritmi scritti;

Per il primo punto, pensavo di indicare il caso base con
$ s(i)={ ( s(i)+1->A>0 ),( ),( ?-> A<0 ):} $

però poi? E poi, il caso base così impostato va bene? Io non sono per nulla convinto.

Potreste aiutarmi, per favore?

[peppe.carbone.90]

[xdom="JoJo_90"]La discussione mi sembra più adatta per la sezione di [strike]Analisi numerica[/strike] Informatica. Sposto.[/xdom]

[hamming_burst]

Ciao,
prova a dare un'occhiata a questo vecchio post: viewtopic.php?f=15&t=69382
ed alle slide: http://profs.sci.univr.it/~posenato/hom ... lgavanzati sul paradigma dinamico, dove viene generalizzato.

entrambi mi furono di aiuto per capire questa tecnica.

[alex170]

ti ringrazio per le letture suggerite. Forse l'ho capita un po' meglio.
Potresti aiutarmi a risolvere il problema che ho postato?

mi è venuta in mente una possibile equazione ricorsiva

$ s(i)={ ( 1-> i=1^^A>0 ),( ),( max{s(i-1)+1,s(i-1)}->i>1^^A>0 ):} $

Spiego:
Se ci sono $i=1$ elementi nell'array la lunghezza del massimo sottoarry è $s(1)=1$
Se ci sono $i>1$ elementi nel'array la lunghezza è il massimo tra $s(i-1)+1$ cioè la massima $s(i)$ fin'ora più il nuovo elemento, se esso è positivo, e $s(i-1)$ cioè la massima $s(i)$ fin'ora senza il nuovo elemento, se esso è negativo.

Può andare bene?

[alex170]

Anzi, meglio

$s(i)={(1→i=1∧A>0),(),(max{s(i−1)+A,A[i+1]}→i>1∧A>0vvA[i+1]>0) :}$

Così aggiungo l'$i$-esimo elemento se $A>0$ oppure $i+1$-esimo ignorando i precedenti se $A<0$ ma $A[i+1]>0$

meglio?