Мне требуется способ найти возрастающую подпоследовательность данного массива, который состоит из различных натуральных чисел от 1 до n случайным образом, после перестановки ровно k подмассивов (непрерывных элементов). Но элементы внутри подмассива не могут быть расположены. В особом случае, если массив отсортирован, вы можете оставить его как есть.
Я подумываю применить алгоритм Longest Increasing Subsequence для (n-k + 1) элементов и расположить остальные соответственно, ноэто было бы очень далеко от правильного ответа.
Я не прошу вас кодировать, но любое разумное объяснение будет полезно для начала.
Заранее спасибо!