Sottosequenze

PREMESSA

Una sequenza può essere pensata come una lista; per esempio la seguente è una sequenza di numeri interi (non necessariamente distinti): [15,6,12,18,9,8,10,20,8,4,7]

Una sottosequenza è una lista che contiene una parte degli elementi di quella originale, posti nello stesso ordine.

Esempi di sottosequenze della lista precedente sono:

  • [15,18,20,4]
  • [15,6,12,18,7]
  • [9,8,10, 8,4,7]

Non è una sottosequenze della lista precedente la seguente:

[15,18,12,9,8,20,10,4,]

perché gli elementi non compaiono nello stesso ordine di quella data (per esempio 18 e 12 oppure 20 e 10.

In certi casi, data una sequenza, è rilevante determinare sottosequenze con certe proprietà; un caso tipico è determinare la sottosequenza più lunga (strettamente) decrescente, o quella (strettamente) crescente, oppure quella i cui elementi godono di certe proprietà.

N.B. “strettamente” indica che non ci sono elementi ripetuti.


PROBLEMA 1

Un bambino ama molto guardare i cartoni animati in TV.
I genitori gli impongono la regola che dopo aver guardato un programma di durata d, può guardare solo programmi di durata minore di d.
Al bambino viene data la Guida TV del suo canale preferito che contiene l’elenco di tutti i programmi della giornata con le relative durate.

Aiutatelo a scegliere il più grande insieme di programmi che può guardare senza infrangere la regola imposta, se la sequenza delle durate dei programmi (espresse in minuti) è la seguente: [7,20,12,14,13,15,8,4]


PROBLEMA 2

Si consideri la sequenza di numeri interi: [8,10,11,12,4,18,6,7,14,10,18,20].
Determinare la più lunga sottosequenza strettamente crescente di numeri pari.