How to find the largest sequence in O(n)?

Question

Algorithms

Hello!
An array of numbers is given, it is necessary to find the length of the longest sequence in it (the sequence can only be with a difference of 1) in O (n)
Actually, here is an example:
1 2 433 500 3 900 4
Therefore, the longest sequence is 4 (1 2 3 4)
AND here's how to implement it all in 1 pass
Maybe some tips/links/articles

Answer 1

banal pass with counting the length of the current sequence

Answer 2

In English. the problem is called " longest increasing subsequence "
Here is a publication of an algorithm for solving this problem for n log n−n log log n + O(n)
Upd. In Russian it is called the Largest Increasing Subsequence Problem (LIS).

Answer 3

https://www.youtube.com/watch?v=t2DpD9GnhfU gurowitz explains more clearly.
Just take the standard algorithm, with the nth item, check its difference in values, and if the difference is 1, then only increase the counter.

Answer 4

Store a hash map where the key is the value of the last element in the sequence encountered earlier, and the value is the length. And then we go through the array and fill it.