Зигзагообразная последовательность

[nikov]

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

Скачок — это разность между соседними элементами.

Если точную наибольшую сумму вычислить трудно, то допустимо приближенное решение. Хотелось бы, чтобы время не очень превышало линейное.

Исправил формулировку
Добавлено спустя 20 минут 29 секунд:

Появилась такая идея: находим минимальный и максимальный элемент. У нас будут 4 точки на горизонтальном отрезке: начало, два экстремума и конец. Они разбивают его на 3 части. Если на каждой из частей скачок больше, чем M, то все 3 части опять рекурсивно пытаемся разбивать. Иначе весь отрезок целиком войдет в результирующий зигзаг.

Добавлено спустя 8 минут 25 секунд:

Нет, так не получится.

[Dandan]

Ну вообще-то идея правильная. Не сложно показать, что существует оптимальное решение, в котором глобальные минимум и максимум не выкинуты. Разбиваем на 3 части используя эти 2 точки. Для каждой части опять ищем глобальные экстремумы (не учитывая концы). Но тут у нас уже на каждой части фиксирован как минимум один конец. Проверяем разности между фиксированными концами и экстремумами. Если одна из разностей меньше необходимой, значит экстремумы брать нельзя и на этой части кроме концов ничего брать нельзя. Иначе делаем рекурсивно.

а хотя да, из-за фиксированных концов будут некоторые проблемы. Ну это я думаю можно исправить не меняя основную идею.

[worm2]

Я думаю, надо сначала искать текущие максимум и минимум, пока модуль разности между текущим экстремумом и начальным значением не достигнет M. Затем точку найденного экстремума объявить новой начальной точкой (и добавить её в последовательность), и искать текущие экстремумы уже на отрезке от этой новой начальной точкой до текущей. Как опять достигли M (скачок по отношению к новой начальной точке), отмечаем новую начальную точку, и если новый экстремум "противоположен" предыдущему (напр., предыдущий был max, а следующий --- min), добавляем её в последовательность. Если же экстремум "того же знака", то удаляем из последовательности предыдущую точку и только потом добавляем новую. И т.д.

[nikov]

Прошу прощения, в формулировке неточность. На самом деле мне надо максимизировать не количество оставшихся скачков, а сумму их модулей.

Добавлено спустя 5 минут 18 секунд:

worm2 писал(а):

Я думаю, надо сначала искать текущие максимум и минимум, пока модуль разности между текущим экстремумом и начальным значением не достигнет M. Затем точку найденного экстремума объявить новой начальной точкой (и добавить её в последовательность), и искать текущие экстремумы уже на отрезке от этой новой начальной точкой до текущей.

Я поправил формулировку задачи. Мне надо максимизировать сумму модулей скачков. Ваш алгоритм для этого не совсем подходит. Например, после обнаруженного максимума (который мы объявляем новой начальной точкой) может быть маленький спуск вниз (меньше M), затем очень большой подъем вверх и новый максимум. Но мы его упустим, так как сейчас мы ищем минимум.

[Dandan]

ну алгоритм с рассмотрением глобальных экстремумов подходит и в этом случае. Кстати, не обязательно на каждом шаге рассматривать и максимум и минимум. На каждом шаге можно рассматривать что-то одно - либо максимум либо минимум. Тогда тоже можно разбивать на части. "Сложный" случай тут будет лишь такой - часть, у которой один конец фиксированный максимум, другой конец - фиксированный минимум, максимум внутри части рядом с концом-максимумом, минимум внутри части рядом с концом-минимумом. Тут уже прийдется рассматривать варианты что включать. Но с использованием мемоизации в итоге вроде не много вариантов получится.

[worm2]

nikov писал(а):

Я поправил формулировку задачи. Мне надо максимизировать сумму модулей скачков. Ваш алгоритм для этого не совсем подходит. Например, после обнаруженного максимума (который мы объявляем новой начальной точкой) может быть маленький спуск вниз (меньше M), затем очень большой подъем вверх и новый максимум. Но мы его упустим, так как сейчас мы ищем минимум.

Э... вроде не совсем так. Я не писал, что мы ищем минимум, а максимумы нас не интересуют.. Я писал, что мы видим, что нашли максимум, поэтому предыдущий максимум удаляем (чтобы минимизировать число скачков), но новый по-любому добавляем. Можно здесь не удалять предыдущий минимум, но тогда ещё и первые разности перестанут быть знакопеременными, а сумма модулей скачков при этом не изменится.
Пусть, например, у нас M = 4. Вот, например, была последовательность:

0, -1, 1, 3, 2, 3, 2, 4, 5, 3, 4, 2, 3, 6, 5, 7, 9, 8, 10, 5, ...

Начинаем с 0 (добавляем в последовательность), ищем либо -4 и менее, либо 4 и более. Нашли 4. Оказался максимум. Добавляем 4 в посл-ть: (0, 4). Ищем либо 0 и менее, либо 8 и более. Наткнулись на 9. Видим, что опять максимум. Можно удалить предыдущую четвёрку, т.к. сумма модулей скачков от этого не изменится: |4-0|+|9-4| = |9-0|. Но следующая 5 - это уже минимум. Поэтому предыдущую девятку удалять нельзя, получается (0, 9, 5), и т.д.

Добавлено спустя 4 минуты 23 секунды:

Правда, мой алгоритм всё равно не без греха: в последовательности
0, 4, 5, 0, ...
он выделит (0, 4, 0), тогда как надо бы (0, 5, 0). Надо такие случаи учесть, но это легко скорректировать: когда нашли второй минимум (0), нужно ещё раз пробежаться и поправить предыдущий максимум.