Сегодняшняя задача дня на Leetcode Самая длинная возрастающая подпоследовательность поставила в тупик. Дан список целых чисел, требуется найти длину самой длинной возрастающей последовательности.

Например для nums = [10, 12, 2, 5, 3, 7, 1, 25, 25, 101, 18, 19, 20] правильный ответ будет 6 (цепочка 2, 3, 7, 18, 19, 20).

Долго крутил в голове, решил нарезать на отдельные возрастающие последовательности и дальше склеивать их, если это удлинит цепочку. Т.е. для примера выше получатся пять цепочек: [10, 12], [2, 5], [3, 7], [1, 25, 101], [18, 19, 20]. Но со склейкой мало того что надо отдельно кучу вариантов прописать, в зависимости от того, как эти интервалы друг относительно друга смещены, но и сам алгорит склейки довольно громоздкий получается (с этим кстати наверняка помогла бы bisect.bisect_left - надо как-то собраться и изучить, что вообще есть полезного в стандартных библиотеках python).

Ну так вот - задача всего лишь medium, а у меня алгоритм получается на две страницы :(. Так ничего и не придумав попроще, пошёл смотреть решения. Очень изящно (правда скорость O(n**2), можно ещё быстрее):

class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums:
            return 0

        n = len(nums)
        dp = [1] * n

        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

Причём, мне уже попадались задачи на этот алгоритм. Сходу вспомнилась: “Есть прямоугольная доска, разбитая на клетки. Муха движется из левого верхнего угла в нижний правый. Перемещения возможны только либо вправо, либо вниз. Сколько всего существует вариантов маршрута?”. Не знаю, как правильно назвать этот алгоритм - обозначил для себя как “Нарастающая сумма” - постараюсь не забывать про него в будущем.

Апдейт от 20 января: паттерн правильно называется Динамическое программирование

И второй вывод из сегодняшней задачи - если решение задачи на соревновании/собеседовании слишком громоздкое или некрасивое - скорее всего это не то решение, которое от тебя ждут.