На одном форуме встретил такое задание для студентов: найти размер максимальной подпоследовательности, элементы которой возрастают по значению. То есть чтобы было понятно, то, например, если дан массив


то для него максимальной подпоследовательностью является { 2, 7, 8, 9 }, размер которой равен 4.

Любопытно, как решить эту простую задачу с помощью стандартныхъ алгоритмов? Естественно ее надо обобщить. 
Найти размер максимальной подпоследовательности, смежные элементы которой удовлетворяют некоторому предикату.
Кто-нибудь пытался решить эту задачу с помощью стандарнтных алгоритмов? У кого какие есть соображения?

И это еще не все. Допустим, вы каким-то образом с использованием стандартных алгоритмов нашли размер максимальной подпоследовательности, удовлетворяющей заданному критерию  в виду предиката. 
Но как теперь имея размер извлечь саму подпоследовательность? Стандартный алгоритм std::search_n не подходит, так как он ищет подпоследовательность заданной длины для фиксированного значения. К тому же предикату не передаются смежные элементы последовательности, а передается лишь заданное значение и значение очередного элемента последовательности.

оно, конечно, можно, но предикат получился такой монстроидальный, что лучше, честно говоря ручками сделать - понятней будет
http://liveworkspace.org/code/83a72ae675f1...7913e88f95215b9

бррр..     

mes, ну, не без того - описался (ударение поставьте сами), а затем воспользовался передовой технологией копипаста 

Кстати, там ошибище. Причём не описка, а именно в алгоритме. Переделывать не хочу. Лень 

Это сообщение отредактировал(а) borisbn - 8.7.2011, 08:39

ну при состовлении такого хитрого предиката вполне возможно не заметить .. уж больно он хитрый получился... 
мне кажется только, что Вы зря мучались, так как для adjacent_find в стл есть свой подходящий предикат..   
правда абсолютно бесхитросный  : 
 http://liveworkspace.org/code/02f672d0356a...2bd3dedb0073cb1
 



Это сообщение отредактировал(а) mes - 8.7.2011, 11:04

mes, да, но в задании требовалось

и

да и цикл

уже не очень соответствует 


P.S. Критиковать всегда проще, чем предложить чего-нибудь  Вот я по простому пути и пошёл   

я не задание решал, а лишь показал что 

  


ага, меня просто сильно "напугал" предикат, поэтому и отвлекся на критику..

 

вообще-то это я про себя говорил 

Надо же, кто-то все-таки откликнулся!

Естественно, первое, что приходит в голову, это использовать два ключевых  шага. 
Первый - это вызов std::adjacent_find с предикатом, как, например,  std::greater<value_type>.

Примечение:


А затем во-втором шаге использовать std::find_if с отрицанием данного предиката, то есть использовать адаптер std::not1.

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

Но проблема состоит в том, что этот алгоритм выдает не совсем то, что требуется. То есть, например, для последовательности



он выдаст значение 5, то есть включит в максимальную подпоследовательность всю последовательность, так как все элементы после первого больше по значению, чем первый элемент.

Ежели строго следовать заданию, то максимальная подпоследовательность - это всего лишь { 1, 3, 5 }, так как 2 уже расположена не по возрастанию после 5.

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

Еще хуже дело обстоит, когда мы знаем размер максимальной подпоследовательность и хотим ее получить по искомому размеру. Алгоритм std::search_n для этих целей не подходит, так как он вызывает предикат не для смежных элементов, чтобы их можно было сравнить, а лишь для текущего значения итератора и заданного константного значения.

Я  сегодня с утра посидел за компьютером и в конечном итоге состряпал 40 разновидностей алгоритма adjacent_find! В большинстве своем они представляют из себя некоторые адаптеры стандартных алгоритмов  При этом в этот набор не входят алгоритмы, которые ищут не просто первый элемент из смежных элементов в последовательности, а весь диапазон смежных элементов.

Спасибо. ВЫ своим кодом меня позабавили! Ваш код в десятки раз сложнее, чем условие задания.

Замечу лишь, что проще написать свой алгоритм



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

Что касается вашего кода, то лишь замечу, что код (раз уж речь зашла об алгоритмах)


    
можно заменить на выхов алгоритма std::copy


 




Это сообщение отредактировал(а) Сыроежка - 8.7.2011, 19:12

Сыроежка, покажите же свою реализацию!

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




Увы, у меня сейчас время закончится. Я вам скорей всего завтра приведу полный цикл. Просто интересно использование отрицание бинарного предиката для поиска конца последовательности.



Завтра весь код покажу. Он достаточно прост и изящен. А для решения задачи в строгом соответсвии с условием я просто, как уже отметил, написал свой алгоритм adjacent_ordered_range, вместо использования adjacent_find и find_if/ 

чего то Вы намутили ?! все нормально должен искать, так как сравнение идет соседних элементов, а не с первым.. 


а зачем загромаждать себя лишним not`ом ? или это иследовательский энтузиазм ?

Итак, на чем я остановился? Ранее я уже набрал

    


Здесь лишнее определение типа value_type. Оно не используется. Поэтому выкидываем его



Теперь продолжим



Если я ничего не напутал, то получился изящный профессионально написанный алгоритм. Можете этот алгоритм от Сыроежки положить в свою копилку алгоритмов. Если его запускать с адаптером std::equal_to, то действительно можно получить размер максимальной последовательности смежных элементов.

Однако, как я уже заметил выше, для адаптеров типа  std::greater или std::less мы получим не возрастающую или убывающую по значению последовательность смежных элементов, а последовательность смежных элементов, каждый элемент которой больше/меньше  первого элемента. Это не ошибка кода, а результат того, что есть два подхода. Либо смежными считать все эелементы, которые удовлетворяют предикату, когда первым аргументом при вызове предиката является значение первого элемента. Либо смежными считать последовательность, все элементы которой попарно удовлетворяют предикату.

И проблема состоит в том, что без написания собственного алгоритма для поиска диапазона упорядоченнных смежных элементов, эту проблему не решить.

Если написать такой алгоритм, то вышеприведенный алгоритм естественно сильно упрощается.