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

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.

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