Самая длинная возрастающая последовательная подпоследовательность | Сет-2

Для заданного массива arr[] из N элементов задача состоит в том, чтобы найти длину самой длинной возрастающей подпоследовательности, разность соседних элементов которой равна единице.

Примеры:

Input: arr[] = {3, 10, 3, 11, 4, 5, 6, 7, 8, 12} 
Output: 6 
Explanation: The subsequence {3, 4, 5, 6, 7, 8} is the longest increasing subsequence whose adjacent elements differs by one.

Input: arr[] = {6, 7, 8, 3, 4, 5, 9, 10} 
Output: 5 

Подход: Наивный подход и подход динамического программирования уже обсуждались в этой статье. В этой статье обсуждается более простой и легкий в реализации подход с использованием хеширования. Идея состоит в том, чтобы сохранить длину подпоследовательности, заканчивающейся текущим целым числом X , в неупорядоченной карте m . Следовательно, если при обходе произойдет X + 1 , длина подпоследовательности будет m[X] + 1 . Максимальное значение на карте m является искомым ответом.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)