Найти длину наибольшей возрастающей последовательности

Question

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

Answer 1

С Википедия: Самая длинная возрастающая подпоследовательность (O ( n log n ))

L = 0
for i = 1, 2, ... n:
   binary search for the largest positive j ≤ L such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
   P[i] = M[j]
   if j == L or X[i] < X[M[j+1]]:
      M[j+1] = i
      L = max(L, j+1)

Answer 2

вы можете использовать динамическое программирование для решения этой проблемы. Решение этой проблемы с использованием динамического программирования здесь:

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

Answer 3

Как предполагает Мерадад, LIS, по крайней мере, близок к тому, что вам нужно. Это наиболее эффективно реализовано с использованием динамического программирования / памятка . Если вас интересуют такие вещи, я рекомендую вам перейти на TopCoder

Answer 4

Не уверен, что вы подразумеваете под алгоритмом, но вот идея.

Если массив отсортирован по умолчанию (т. Е. При создании массива самое длинное значение находится в конце из-за возрастающей последовательности), тогда извлекается последнее значение массива.

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