Let $f$ be a permutation on $n$ letters. I want to count the number of $k$-long increasing subsequences quickly.
First I use divide and conquer to split the problem into finding increasing subsequences in pairs of numbers. The resulting 'tree' has height $\log n$. I'm wondering how I can combine the subproblems in an efficient way. I thought about prefix sums and using mergesort, but I can't see how to effectively implement them.
One idea to save time when combining two subproblems is to compare elements at the end of your increasing subsequences in your first subproblem with the values in your second subproblem.
My goal is to get to $O(kn\log n)$ time but this doesn't do it.
