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

@ProgrammerDuck · Регистрация: 18.10.2016

Студворк — интернет-сервис помощи студентам

Задача о поиске наибольшей чередующейся подпоследовательности.

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

@Shamil1 · 29.06.2017, 10:16

Не понятно, причём здесь динамическое программирование. На первый взгляд, задача решается за один проход. Храним и используем значение последнего элемента и направление (вверх или вниз).

Есть примеры данных с ответами для проверки правильности решения?

@Massaraksh7 · 29.06.2017, 12:47

Сообщение от Shamil1

Не понятно, причём здесь динамическое программирование.

Очевидно, ТС имел в виду программирование динамических рядов.

Сообщение от Shamil1

На первый взгляд, задача решается за один проход. Храним и используем значение последнего элемента и направление (вверх или вниз).

И индекс начала очередной последовательности.

@Shamil1 · 29.06.2017, 13:35

Сообщение от Massaraksh7

И индекс начала очередной последовательности.

Все подпоследовательности начинаются с первого элемента.
Самая длинная подпоследовательность будет начинаться с первого элемента и заканчиваться последним.

Добавлено через 16 минут
Что-нибудь типа этого:

C#
1
2
3
struct Data { public int Last, MaxLen; public bool? Up; }
Data Step(Data s, int x) => s.Last != x ? new Data {Last = x, Up = x > s.Last, MaxLen = s.MaxLen + Convert.ToInt32(x > s.Last)} : s;
int Length(IEnumerable<int> sec) => sec.Skip(1).Aggregate(new Data { Last = sec.First(), MaxLen = 1 }, Step).MaxLen;

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@ProgrammerDuck 0 / 0 / 0 Регистрация: 18.10.2016 Сообщений: 3

	Метод динамического программирования для задачи поиска наибольшей чередующейся подпоследовательности 26.06.2017, 19:52. Показов 5754. Ответов 3 Метки нет (Все метки) Задача о поиске наибольшей чередующейся подпоследовательности. Имеется последовательность. Необходимо определить самую длинную пилообразную подпоследовательность. Подпоследовательность получается из последовательности путем вычеркивания из последовательности некоторого количества элементов. Любая последовательность является подпоследовательностью для самой себя. Пустая последовательность является подпоследовательностью для любой последовательности. Последовательность называется пилообразной, если любой элемент или больше, или меньше всех своих соседей. 0

@Shamil1 Модератор 3135 / 2282 / 469 Регистрация: 26.03.2015 Сообщений: 8,884
	29.06.2017, 10:16
	Не понятно, причём здесь динамическое программирование. На первый взгляд, задача решается за один проход. Храним и используем значение последнего элемента и направление (вверх или вниз). Есть примеры данных с ответами для проверки правильности решения? 0