Почему это работает
- У любой возрастающей цепочки длиннее одного числа, которая кончается на nums[i], есть число прямо перед nums[i] — какое-то меньшее nums[j] с j < i. Отрежем nums[i], и останется цепочка, которая кончается на nums[j], длиной не больше lis[j]. Значит, lis[i] = 1 + наибольшее такое lis[j].
- Это j может стоять где угодно до i, поэтому проверяются все прежние числа, а не только сосед: для 6 стоящая прямо перед ней 2 даёт 2, а 5 за два места до неё — 3.
- Лучшая цепочка может кончаться где угодно, поэтому ответ — наибольшая клетка, а не последняя: здесь lis кончается на 2, а цепочка 4, 5, 6, 7 кончается на индексе 5.
Сложность
Время O(n²): каждое число один раз смотрит на все числа перед собой. Память O(n): по клетке на число. Есть способ быстрее, O(n log n): хранить наименьший конец цепочки каждой длины и искать место для числа двоичным поиском.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗