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

Se constrieste 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.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")==