Let (k,\(\ell)\) denote the class of permutations \(\pi =(\pi (1),...,\pi (n))\) which can be partitioned into k increasing and \(\ell\) decreasing subsequences. Let \(P(\pi)=\min \{k+\ell:\pi\in (k,\ell)\) and \(P(n)=\max_{\pi \in {\mathfrak S}_ n}P(\pi)\). It is shown that \(P(n)=\lceil \sqrt{2n+\frac{1}{4}}+\frac{1}{2}\rceil\). The problem ”\(\pi\in (k,\ell)''\) can be solved in \({\mathcal O}(n^{k+\ell})\) steps using breadth-first search. For the special case ”\(\pi\in (k,1)''\) an algorithm is given which solves the problem in \(C\cdot (k+1)^{(k+1)}n\cdot \log n\) steps and thus works in \({\mathcal O}(n \log n)\) time for all fixed k. Since increasing (decreasing) subsequences of permutations corresponding to independent sets (cliques) in permutation graphs there are close connections to properties of permutation graphs.