Hints

Solution

Denote the length of the Longest Increasing Subsequence for the whole permutation by \(L\). For every position \(i\), precalculate the length of the longest increasing subsequence ending in it, \(f(i)\).

Now, if \(L\) is even, the split is always possible: into the first subsequence put indexes \(i\) with \(f(i)\le \frac{L}{2}\) and all the remaining to the other. It’s clear that they both have length of the longest increasing subsequence equal to \(\frac{L}{2}\).

If \(L = 2K+1\), under any split some subsequence will contain an increasing subsequence of length at least \(K+1\), so we must have \(LIS\ge K+1\) in both subsequences. Consider any longest increasing subsequence of permutation of this length \(2K+1\). There has to be an element, that isn’t among these elements, but is in increasing subsequence of length at least \(K+1\).

This turns out to be sufficient. Indeed, suppose that element at position \(x\) is not from longest increasing subsequence of the permutation, but is in increasing subsequence of length \(K+1\). Suppose that elements of this subsequence are at positions \(i_1, \dots, i_{K+1}\). Then, divide the elements as follows:

• If $f(i)$ is different from all of $f(i_1), f(i_2), \dots, f(i_{K+1})$, element at position $i$ goes to the first subsequence.
• If $f(i) = f(x)$ and $i\neq x$, element at position $i$ goes to the first subsequence.
• All other elements go to the second subsequence.

Note that the second subsequence contains this increasing subsequence of length \(K+1\) containing element at position \(x\), but can’t contain longer incresing subsequence. First subsequence contains \(K+1\) elements from entire LIS, but can’t contain larger increasing subsequence as well.

To check if there exists an element not from LIS which is in increasing subsequence of length at least \(K+1\), for each element calculate the length of the longest increasing subsequence ending and starting in it, and count the number of elements for which sum of these 2 values is at least \(K+2\). For “YES”, there have to be at least \(2K+2\) of them.