== 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 $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>