== include(page="template/taskheader" task_id="sandwich") ==

Poveste şi cerinţă...
 

În Ţinutul Ooo, Jake vrea să pregătească sandwichul magic perfect. Pe o potecă sunt aliniate $n$ ingrediente numerotate de la $1$ la $n$, iar ingredientul $i$ are o valoare de „gust” $a[i]$. Magia sandwichului are o regulă ciudată: nu are voie să aleagă două ingrediente alăturate, altfel magia se risipeşte.

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:

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[i1] + a[i2] + ... + a[ik],  cu  l ≤ i1 < i2 < ... < ik ≤ 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).