# Disjoint $k$ Increasing Subsequences

Given a permutation $$P$$ and an integer $$k$$, we need to devise an algorithm which finds the $$k$$ disjoint increasing subsequences (say $$L_1,L_2\ldots, L_k$$) such that the sum total of their lengths (say $$S_k$$) is maximum is over any choice of $$k$$ disjoint increasing subsequences from a permutation $$P$$. For simplicity, one can assume that $$k$$ is atmost than the length of the longest decreasing subsequence.

For example consider $$P=[4,1,2,7,5,6,3]$$

Here if $$k=1$$, then longest increasing subsequence is of length 4 (i.e $$S_1=4$$) which corresponds to the subsequence [1,2,5,6]

Here if $$k=2$$, then the maximum length of two disjoint increasing subsequences is 6 (i.e $$S_2=6$$) which corresponds to the two disjoint increasing subsequences [1,2,3] and [4,5,6].

Possibly simple question

Is there an $$O(n$$poly log $$n)$$ algorithm which can keep track of the values $$S_1,S_2\ldots,S_k$$ under insertions?

Possibly harder question

Is there an $$O(n$$poly log $$n)$$ algorithm which can keep track of the values as well as the increasing subsequences corresponding to $$S_1,S_2\ldots,S_k$$ under insertions?

• Is it possible to compute $S_2$ in $o(n^2)$ time? Is it possible to compute $S_3$ in $O(n^2)$ time? Jul 18, 2022 at 18:12
• What are the best algorithms you have been able to find so far? What's the fastest you know how to solve this in the static case, where there is only a single value of $P,k$?
– D.W.
Jul 18, 2022 at 19:09