h1. 'Concert2':problema/concert2
Problema se rezolva cu ajutorul programarii dinamice:

Se construieste dinamica

* $dp[i][j][p]$ = lungimea maxima a unui subsir care respecta proprietatile din enunt si se termina pe pozitia $i$ iar ultima secventa crescatoare are lungimea $j$ pentru $p = 0$ si lungimea maxima a unui subsir care respecta proprietatile din enunt si se termina pe pozitia $i$ iar ultima secventa descrescatoare are lungimea $j$ pentru $p = 1$.

* dp[i][j][p]= lungimea maxima a unui subsir care respecta proprietatile din enunt si se termina pe pozitia i iar ultima secventa crescatoare are lungimea j pentru p = 0 si lungimea maxima a unui subsir care respecta proprietatile din enunt si se termina pe pozitia i iar ultima secventa descrescatoare are lungimea j pentru p = 1.

O recurenta in $O(N)$ nu se incadreaza in timp, de aceea va trebui sa construim $2*K$ arbori de intervale pentru a putea calcula in timp logaritmic maximul pe un interval.Pentru asta este necesar sa normalizam datele de intrare. Solutia se gaseste in maximul din aceasta matrice.