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.
Solutia se gaseste in maximul din aceasta matrice.

Complexitate : O(N * logN *K)

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