Mi è capitato un paio di giorni fa di incontrare di nuovo questo problema:

data una lista di valori numerici sia positivi che negativi, si trovi la sottosequenza di valore massimo

Anche se in realtà in questa incarnazione era “data una lista di aumenti/perdite nella valutazione di un titolo”, che però la rende solo più contorta per il fatto di usare le percentuali.

Ora, ad una prima occhiata questo problema si risolve con un algoritmo che ha complessità O(n2), ma io ricordavo da discussioni precedenti (sul blog di matteo vaccari e su #verbamanent, era stato usato durante un colloquio di lavoro) che esiste un algoritmo con complessità lineare.

Sicché mi son ritrovato a impicciarmi paurosamente il cervello mentre cercavo di leggere Snow Crash && facevo il bagno.
Se volete provare a risolvere il problema da voi smettete di leggere qui, per ora.

Nel mio cervello girava l’idea che dovesse essere possibile farlo tenendo traccia soltanto dell’ultimo valore massimo e del valore attuale, ma non riuscivo a visualizzare bene la cosa. Dopo 45 minuti di bagno ho deciso che forse era meglio mettermi davanti a un editor per vedere cosa veniva fuori.. e siccome quando le cose non sono importanti sono una persona seria ho cominciato a programmare in modalità test driven, partendo inizialmente con questi test (giuro che ho fatto una cosa per volta, ma qui velocizzo, uso il mio “microunit”, ma dovrebbe essere chiaro )

def maxseq(*args)
  total=0
  args.each {|el| total+=el}
  total
end
	
t do
  is maxseq(0), 0
  is maxseq(1), 1
end

E fin qui tutto bene. Ci si aspetta però che per una sequenza con soli numeri negativi il risultato migliore sia non prendere niente (o nel caso originale, non investire una lira), quindi ho aggiunto is maxseq(-1),0, beccandomi il mio simpatico fallimento:

Loaded suite maxseq
Started
F
Finished in 0.006429 seconds.
	
  1) Failure:
test_1()
    [./tu.rb:17:in `test_1']:
<0> expected but was
<-1>.

ok, questo è facile da sistemare:

def maxseq(*args)
  total=0
  args.each {|el| total=[total+el,0].max}
  total
end

Vabè, fin qui era tutto semplice, ma adesso proviamo a mettere un po’ di vere sequenze:

  is maxseq(1,2,3), 6
  is maxseq(1,-2,3), 3
  is maxseq(1,2,-3), 3

La prima assertion funziona, e questo era previsto. Inaspettatamente funziona anche la seconda, mentre la terza fallisce, <3> expected but was <0>. Questo errore è chiaramente dovuto al mio test scemo, che si limita a ridurre a zero il totale quando incontra un numero negativo, e la soluzione sta quindi nel mantenere, in questo caso, il valore precedente.
Rinomino quindi la variabile total in current, e modifico il codice aggiungendo un ulteriore max:

def maxseq(*args)
  total=0
  current=0
  args.each do |el|
    current=[current+el,0].max
    # voglio total.= come in perl6 !
    total=[total,current].max
  end
  total
end

Il codice a questo punto tiene traccia di un intervallo tramite il valore di current, che si resetta a 0 tramite il max (nella mia mente annebbiata da vapore & cyberpunk avevo introdotto if come se piovesse) e allo stesso tempo aggiorna il valore totale solo se si è trovato un intervallo migliore.
Questo codice passa il test. E la cosa bella, è che funziona anche con i test seguenti, finché la mia minima suite di test diventa:

t do
  is maxseq(0), 0
  is maxseq(1), 1
  is maxseq(-1),0
  is maxseq(1,2,3), 6
  is maxseq(1,-2,3), 3
  is maxseq(1,2,-3),3
  is maxseq(-1,2,3),5
  is maxseq(-1,-2),0
  is maxseq(1,-2,3,4,-5,6,-7),8
  is maxseq(1,-2,-3,6),6
  is maxseq(0,1,-2,-3,5,6),11
end

Ora, questi test sembrerebbero coprire i casi possibili, e il codice risultante ha complessità Θ(n), che va benissimo, e potrei ridurre il corpo del metodo a due righe (o a una sola, ma bruttina).
Posso anche fare il fighetto dicendo che il TDD effettivamente aiuta a trovare il design migliore… anche se ammetto di non sentirmi troppo sicuro.
Il codice copre tutti i casi che mi vengono in mente, ma non ho fatto un’analisi seria per saper se effettivamente restituisce sempre un risultato corretto. E qua rientra alla grande il post di matteo, che dice che questo è un esempio classico in cui applicare la program derivation, insomma trovare una soluzione ottima e avendo la certezza che sia corretta per costruzione.

Cavolo quanta roba devo ancora imparare sulla programmazione (spazio intenzionalmente lasciato senza faccina perché la cosa è sia bella che brutta)