Pentru orice segment continuu de ingrediente $a{~l~} a{~l+1~} ... a{~r~}$, Jake poate alege un subşir de poziţii strict crescător (eventual gol) astfel încât nici două poziţii alese să nu fie adiacente. Suma gustului acelui subşir este: $a{~i{~1~}~} + a{~i{~2~}~} + ... + a{~i{~k~}~}$, cu $l ≤ i{~1~} < i{~1~} < ... < i{~k~} ≤ $r$ şi i{~j~} + 1 < i{~j+1~}$

Definim $f(a[l..r])$ = suma maximă posibilă pentru un astfel de subşir (se permite subşirul gol).

Definim <tex> f(a[l..r]) </tex> = suma maximă posibilă pentru un astfel de subşir (se permite subşirul gol).

Jake vrea să ştie câtă magie totală poate aduna, dacă ia în calcul toate segmentele posibile ale potecii. Cu alte cuvinte, calculaţi: