0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Is it possible to compute $S_2$ in $o(n^2)$ time? Is it possible to compute $S_3$ in $O(n^2)$ time? $\endgroup$
    – John L.
    Jul 18, 2022 at 18:12
  • $\begingroup$ 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$? $\endgroup$
    – D.W.
    Jul 18, 2022 at 19:09

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.