(Challenge) Maximizing LIS

You are given an integer $K$ and a random permutation ― sequence $A_1, A_2, \ldots, A_N$ of integers $1$ through $N$. You have to perform the following process: 1. Split the permutation $A$ into $K$ non-empty contiguous subsequences $S_1, S_2, \dots, S_K$ such that each element of $A$ appears in exactly one of them. 2. Choose an arbitrary permutation $P$ of the integers $1$ through $K$. 3. Create