Минимальное число неубывающих подпоследовательностей
Сортировка
Экстремальная
Дан массив nums. Разбейте его на минимальное число подпоследовательностей (не обязательно непрерывных), каждая из которых НЕ убывает. Верните это минимальное число.
По теореме Дилворта это число равно длине наибольшей СТРОГО убывающей подпоследовательности исходного массива.
Сигнатура функции
min_partitions(nums: list[int]) -> int
Примеры
| Вход | Ожидаемый результат |
|---|
| [[5, 4, 3, 2, 1]] | 5 |
| [[1, 2, 3, 4, 5]] | 1 |
1решили
1пытались
100%успешность
Войдите, чтобы решить →