Удалить несортированные/выпадающие элементы в почти отсортированном массиве

Я бы свел вашу проблему к самой длинной проблеме возрастающей (убывающей) подпоследовательности.

https://en.wikipedia.org/wiki/Longest_increasing_subsequence

Поскольку ваша последовательность почти отсортирована, вы гарантированно получите удовлетворительный результат (т. е. точное следование линии тренда).

Существует ряд решений; один из них описан в бесплатной книге "Основы компьютерного программирования на C#. Светлина Накова и Веселина Колева; задача представлена ​​на странице 257, упражнение 6; решение на странице 260.

Взято из книги:

Напишите программу, которая находит максимальную последовательность возрастания элементов в массиве arr[n]. Нет необходимости, чтобы элементы располагались последовательно. Например: {9, 6, 2, 7, 4, 7, 6, 5, 8, 4} -> {2, 4, 6, 8}.

Решение:

Мы можем решить проблему с помощью двух вложенных циклов и еще одного массива len[0…n-1]. В массиве len[i] можно сохранить длину самой длинной последовательно возрастающей последовательности, которая начинается где-то в массиве (неважно, где именно) и заканчивается элементом arr[i]. Следовательно, len[0]=1, len[x] — это максимальная сумма max(1 + len[prev]), где prev ‹ x и arr[prev] ‹ arr[x]. Следуя определению, мы можем вычислить len[0…n-1] с двумя вложенными циклами: внешний цикл будет перебирать массив слева направо с переменной цикла x. Внутренний цикл перебирает массив от начала до позиции x-1 и ищет элемент prev с максимальным значением len[prev], где arr[prev] ‹ arr[x]. После поиска мы инициализируем len[x] 1 + наибольшее найденное значение len[prev] или 1, если такое значение не найдено.

Описанный алгоритм находит длины всех максимальных возрастающих последовательностей, которые заканчиваются на каждом из элементов. Наибольшее из этих значений — это длина самой длинной возрастающей последовательности. Если нам нужно найти сами элементы, составляющие самую длинную последовательность, мы можем начать с элемента, где заканчивается последовательность (с индексом x), мы можем распечатать его и найти предыдущий элемент (prev). По определению prev ‹ x и len[x] = 1 + len[prev], поэтому мы можем найти prev с помощью цикла for от 1 до x-1. После этого мы можем повторить то же самое для x=prev. Находя и печатая предыдущий элемент (prev) много раз, пока он не существует, мы можем найти элементы, составляющие самую длинную последовательность в обратном порядке (от последнего к первому).

Простой алгоритм, описанный Игуаро, может помочь вам сгенерировать правильную последовательность:

Для каждого элемента с индексом i, если a[i] < a[i + 1], мы можем просто удалить этот элемент a[i].

for(int i = 0; i < size; i++)
    while(a[i] < a[i + 1]){
       remove a[i];
       i--;
    }

Однако этот подход не может гарантировать минимальное количество удаляемых элементов. Например, для этой последовательности [10, 9, 8, 100, 1, 0] удаление 100 будет оптимальным вместо удаления 8, затем 9, затем 10.

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