Как найти наибольшую поседовательность за O(n)?

Question

[Алексей Майрин]

Всем привет!
Дан массив чисел, в нем необходимо найти длину самой длинной последовательности(последовательность может быть только с разнице на 1) за O(n)
Собственно вот пример:
1 2 433 500 3 900 4
Следовательно длинная самая последовательность 4(1 2 3 4)
И вот как это все реализовать за 1 проход
Может какие-то наводки/ссылки/статьи

Comments

[Alex Setup]

Эта последовательность (с разницей 1) должна обязательно с 1 начинаться?

[Сергей Соколов]

Alex Setup, боюсь, что нет. Начинаться может с любого значения.

[Alex Setup]

Сергей Соколов, А ну тогда задача интересна.

[Alex Setup]

Сергей Соколов, Я не уверен что она будет решаться за линию

[Алексей Майрин]

Alex Setup, раз дали, значит должна) плюс снизу ссылки с алгоритмами

Answer 1

[Дмитрий]

банальным проходом с подсчетом длины текущей последовательности

Comments

[Алексей Майрин]

Так а как?если числа последовательности могут быть в разных местах массива?
или чего-то не понял?

[Сергей Соколов]

в худшем случае это будет больше, чем O(n), т.к. на каждое очередное число придётся искать, не является ли оно +1 от кого-то из встреченных ранее.

[Дмитрий]

Сергей Соколов,
зачем искать то?
явно же автор опечатался в описании
потому что последовательность по определению состоит из последовательно расположенных элементов.

[Дмитрий]

Алексей Майрин,
тогда это не будет последовательностью
но если вам так хочется нужно всего лишь запоминать какое число из "последовательности" уже попадалось и искать число большее на единицу

[Алексей Майрин]

Дмитрий, числа же могут быть в разном порядке в массиве

[Дмитрий]

в массиве могут а в последовательности нет
сейчас лень
но если что завтра код набросаю
на каком языке понятнее будет?

[Алексей Майрин]

Дмитрий, да в принципе на любом пойму)

[Дмитрий]

//arr[0..n] массив в котором будет производится поиск
//current_length длина текущей последовательности
//max_start,max_length начало и длина наибольшей последовательности
current_start:=0;
current_length:=1;
max_start:=0;
max_length:=0;
for i:=1 to n do//начиная со второго элемента 
if arr[i]=arr[i-1]+1 then 
   begin//если элемент больше предыдущего на 1
      current_length:=current_length+1;
   end
else
   begin
       if current_length>max_length then
          begin
             max_length:=current_length;
             max_start:=i-1-current_length;//пишется с головы поэтому смещение может быть не верным
             current_length:=1;
          end;
   end;
//на случай если конец самой длинной последовательности совпадает с концом массива
if current_length>max_length then
          begin
             max_length:=current_length;
             max_start:=n-current_length;//пишется с головы поэтому смещение может быть не верным
             end;

Answer 2

[Сергей Соколов]

На англ. проблема называется "longest increasing subsequence"

Вот публикация алгоритма решения этой проблемы за n log n−n log log n + O(n)

Upd. По-русски называется Задача о наибольшей возрастающей подпоследовательности (НВП).

Comments

[Алексей Майрин]

Немного не так наверное, решение с хэш таблицей как раз и даст o(n)

[Astrohas]

Алексей Майрин, вам нужно учитывать и сами внутренные операции хэш таблиц. А они не бесплатные.

Answer 3

[Astrohas]

https://www.youtube.com/watch?v=t2DpD9GnhfU гуровиц объясняет более внятно.
Просто берете стандартный алгоритм, при n-ом итеме проверяете его разницу в значениях и если разница равно 1 то только тогда увеличиваете счетчик.

Comments

[Алексей Майрин]

Там все за n^2 (

[Astrohas]

Алексей Майрин, все алгоритмы за n2. Этот алгоритм можно ускорить максимум до NLogN, но не быстрее, но тогда в этом случае посик самой последовательнсоти будет очень сложен

Answer 4

[tsarevfs]

Хранить hash map, в которой ключ - значение последнего элемента в последовательности встреченной раньше, а значение -- длина. И дальше проходим по массиву и заполняем.

Comments

[Алексей Майрин]

А значение длинна, длинна чего? Самой длинной последовательности?

[Руслан .]

Длинна текущей последовательности. В этом hash map каждый ключ это отдельная последовательность а значение это ее длинна. Если брать ваш пример то как тот будет:
Шаг 1
Ключ = 1 значение = 1
Шаг 2
Ключ = 2 значение = 2 потому что мы продолжаем последовательность начатую на шаге 1
Шаг 3
Уже имеем две последовательности
Ключ = 2 значение 2
Ключ = 433 значение = 1
Шаг 4
Ключ = 2 значение = 2
Ключ = 433 значение = 1
Ключ = 500 значение = 1
Шаг 5
Ключ = 3 значение = 3
Ключ = 433 значение = 1
Ключ = 500 значение = 1
Шаг 6
Ключ = 3 значение = 3
Ключ = 433 значение = 1
Ключ = 500 значение = 1
Ключ = 900 значение = 1
Шаг 7
Ключ = 4 значение = 4
Ключ = 433 значение = 1
Ключ = 500 значение = 1
Ключ = 900 значение = 1
Т.е. на каждом шаге мы берём один элемент из массива и либо удлиняем имеющуюся цепочку, либо начинаем новую.