h1. 'Concert2':problema/concert2

Problema se rezolva cu ajutorul programarii dinamice:
 
* $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.
 
Complexitate : $O(N * logN *K)$
 

==include(page="template/monthly-2014/footer")==