h1. Hapsan

Problema cere găsirea unui subşir crescător de sumă maximă, cu respectarea a $M$ constrângeri de forma _putem alege un singur element din intervalul [Ai...Bi]_.
Fie dinamica intuitivă $dp[i] = "cel mai bun câştig, considerând că ultimul sushi a fost cel cu indicele de ordine i"$.
Pentru a rezolva problema, o spargem în două subprobleme:
 
* rezolvarea restricţiilor pe interval : Se poate rezolva preprocesând $left[i] = $"cel mai din dreapta sushi pe care îl pot lua ca penultim, dacă ultimul sushi luat a fost $i$". Se demonstrează că $left[i] = min{Aj | Aj <= i <= Bj} - 1$. Acest lucru se poate calcula în mai multe moduri : cu deque / baleiere / arbore de intervale. Există totuşi o soluţie care rezolvă problema în timp liniar, folosindu-se doar de un array ca structură auxiliară, pe care o lăsăm ca temă de gândire.
 
* rezolvarea restricţiilor de monotonie : Se poate rezolva în două moduri, folosind un AIB / arbore de intervale. Unul este sortând în prealabil sushi-urile crescător şi rezolvându-le în ordinea sortată, rezolvarea fiind modelată ca şi query de **maxim pe prefix**.
 

h1. Shield
h1. Cutit