Partition a permutation into monotonic subsequences
You are given a permutation of size \(n\), i.e. a sequence of \(n\) distinct numbers. The task is to partition this permutation into monotonic subsequences. The number of subsequences (syn.: partition) does not need to be minimum, but it has to be smaller than \(f(n)\), which denotes the minimum \(k\) such that any permutation of size \(n\) can be splited into at most \(k\) subsequences.
I came across this problem on Codeforces a while ago. They did provide a solution (thanks, Radewoosh!), but since I love to proving things, I want to note down some of my insights and findings.
>> View post