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

Например, длина LIS для {10, 12, 9, 13, 21, 50, 41, 65, 85} равна 7, а LIS - {10, 12, 13, 21, 50, 65, 85}.

Эту проблему можно решить со сложностью O (n²) с помощью рекурсии или динамического программирования.
Но есть другой подход, который может решить эту проблему со сложностью O (nlogn) с пространственной сложностью O (n) (в худшем случае, когда последовательность в порядке возрастания).

Давайте углубимся в подход:
Код очень короткий и простой для понимания.

import bisect
def lis(arr):
  if len(arr) == 0:
    return 0
  l = [arr[0]]
  
  for element in arr[1:]:
    pos = bisect.bisect(l, element)
    if pos == len(l):      
      if element > l[pos - 1]:
        l.append(element)
    else:
      if element != l[pos - 1]:
        l[pos] = element
  return len(l)
if __name__ == "__main__":
  print(lis([10, 12, 9, 13, 21, 50, 41, 65, 85]))

Как это работает ?

Концепция заключается в том, что для каждого элемента в списке мы проверяем, где он находится в самом длинном списке подпоследовательностей (результирующий массив).
Для этого может быть 2 случая:

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

Этот метод работает, потому что мы всегда добавляем новое число в возрастающей последовательности.

Вышеупомянутый результат получен из leetcode, который проверяет программу и показывает время выполнения и потребляемую память.

Примечание: эту программу можно использовать только для подсчета длины самого длинного массива подпоследовательностей. Если нам нужна фактическая последовательность, нам нужно использовать двумерный массив для хранения последовательности для каждой длины. Обычно на соревнованиях по программированию нас интересует только длина самой длинной последовательности.

Тем не менее, если вас интересует сама последовательность, проверьте код ниже:

    def lis_nlogn(arr):
        if len(arr) == 0:
          return 0
        
        l = [[arr[0]]]
        for element in arr[1:]:
            pos = bisect.bisect(l[-1], element)
            if pos == len(l):
                if element > l[pos - 1][pos - 1]:
                    l.append(l[pos -1] + [element])
            elif pos == 0:
                l[pos][pos] = element
            else:
                if element != l[pos - 1][pos -1]:
                    l[pos][pos] = element
        return len(l)
## l contains the actual sequence

При таком подходе время выполнения составляет 60 мс, а потребление памяти увеличивается до 38,4 МБ для того же набора тестовых примеров.

Обязательно используйте первую программу, если нас интересует длина, а не фактическая последовательность.