В мире алгоритмов и решения задач задача о самой длинной возрастающей подпоследовательности (LIS) занимает особое место. Программистам предлагается найти самую длинную подпоследовательность заданной последовательности, которая строго возрастает. В этой статье мы рассмотрим различные методы решения этой проблемы, используя разговорный язык и попутно предоставляя примеры кода.

Метод 1: подход грубой силы
Давайте начнем с самого простого подхода — метода грубой силы. Мы сгенерируем все возможные подпоследовательности и проверим каждую на предмет возрастания порядка. Хотя этот метод неэффективен для больших входных данных, он обеспечивает основу для понимания проблемы.

def longest_increasing_subsequence(nums):
    n = len(nums)
    max_length = 0
    for i in range(n):
        for j in range(i, n):
            subsequence = nums[i:j+1]
            if all(subsequence[k] < subsequence[k+1] for k in range(len(subsequence)-1)):
                max_length = max(max_length, len(subsequence))
    return max_length
# Example usage
sequence = [3, 10, 2, 1, 20]
result = longest_increasing_subsequence(sequence)
print(result)  # Output: 3

Метод 2: динамическое программирование
Подход грубой силы можно оптимизировать с помощью динамического программирования. Мы создадим вспомогательный массив dpдля хранения длины самой длинной возрастающей подпоследовательности, заканчивающейся каждым индексом. Итеративно обновляя dp, мы можем найти самую длинную возрастающую подпоследовательность.

def longest_increasing_subsequence(nums):
    n = len(nums)
    dp = [1] * n
    max_length = 1
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
        max_length = max(max_length, dp[i])
    return max_length
# Example usage
sequence = [3, 10, 2, 1, 20]
result = longest_increasing_subsequence(sequence)
print(result)  # Output: 3

Метод 3: двоичный поиск с помощью массивов
Другой эффективный подход — использовать двоичный поиск вместе с массивами. Мы будем поддерживать массив tailsдля хранения наименьших значений хвоста всех найденных на данный момент возрастающих подпоследовательностей. Обновив tailsстратегически, мы сможем найти самую длинную возрастающую подпоследовательность.

import bisect
def longest_increasing_subsequence(nums):
    tails = [float('inf')] * (len(nums) + 1)
    tails[0] = float('-inf')
    max_length = 0
    for num in nums:
        index = bisect.bisect_left(tails, num)
        tails[index] = num
        max_length = max(max_length, index)
    return max_length
# Example usage
sequence = [3, 10, 2, 1, 20]
result = longest_increasing_subsequence(sequence)
print(result)  # Output: 3

В этой статье мы рассмотрели три различных метода решения проблемы самой длинной возрастающей подпоследовательности. Мы начали с подхода «грубой силы», за которым последовали метод динамического программирования и метод двоичного поиска с использованием массивов. Каждый метод имеет свои преимущества и сложности, что делает их полезными в разных сценариях.