readings показания датчика в том порядке, в каком они поступали. Аналитик хочет вычеркнуть часть записей так, чтобы оставшиеся шли строго по возрастанию, и при этом сохранить как можно больше записей. Порядок оставшихся менять нельзя, а вот идти подряд в исходном массиве они не обязаны.
Верните наибольшее количество записей, которое можно оставить.
Решение за O(n²) несложное — попробуйте уложиться в O(n log n).readings=[4, 12, 3, 6, 5, 9, 1] → 3
Можно выбрать 4, 6, 9 или 3, 5, 9 — длина 3. Четырёх строго растущих значений по порядку здесь нет.
readings=[-2, 0, 0, 1, -5, 2] → 4
-2, 0, 1, 2 — длина 4. Два нуля подряд взять нельзя: рост должен быть строгим.
readings=[5, 5, 5] → 1
Все значения равны, поэтому выбрать можно только одно.
readings=[4, 12, 3, 6, 5, 9, 1]
3
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 136 тестов на сервере, включая скрытые.