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

Î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.

Î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 <tex> a_l, </tex>, <tex> a_{l+1}, </tex>, ..., </tex> a_r <tex>, 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:

<tex> a_{i_1} <tex> + <tex> a_{i_2} <tex> + ... + <tex> a_{i_k} <tex>, cu l &le; <tex> i_1 <tex> &lt; <tex> i_2 <tex> &lt; ... &lt; <tex> i_k <tex> &le; r şi <tex> i_j <tex> + 1 &lt; <tex> i_{j+1} <tex>
Definim f(a[l..r]) = suma maximă posibilă pentru un astfel de subşir (se permite subşirul gol).