Минимальные удаления в массиве, чтобы разница между соседними элементами не уменьшалась

Учитывая массив A из N неотрицательных целых чисел, задача состоит в том, чтобы вычислить минимальное количество элементов, которые нужно удалить, чтобы выполнялись следующие условия:

• Элементы расположены в неубывающем порядке. (Формально для каждого i (1 ≤ i ≤ N-1) должно выполняться условие A _i+1 >= A _i .)
• Разница между соседними элементами должна быть в неубывающем порядке. (Формально для каждого i (2 ≤ i ≤ N-1) должно выполняться условие A _i -A _i-1 ≤ A _i+1 -A _i .)

Примеры:

Input: A = {1, 4, 5, 7, 20, 21}
Output:
 2
Explanation: By deleting 5 and 21, the array {1, 4, 7, 20} is obtained. Here the elements are in non-decreasing order and the difference between adjacent elements are 3, 3, 13 which are in non-decreasing order. 

Input: A = {3, 2}
Output: 
1
Explanation: The original array doesn’t satisfy the first condition. Hence, either of the elements can be deleted to get an array with a single element.

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

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N* ^2N )
Вспомогательное пространство: O(N)

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

1. Создайте двухмерный массив dp , где dp[i][j] хранит минимальное количество удаляемых элементов от индекса 1 до i , которые удовлетворяют условию:
   1. А[я]-А[я-1]=А[j]
2. Итерируйте от 0 до N-1 , используя i , и сделайте следующее:
   1. Сохраните 1 в dp[i][0] , так как размер будет 1 .
   2. Итерируйте от i-1 до 0, используя j , и сделайте следующее:
      1. Проверьте, больше ли A[i] , чем A[j]. Если больше, делаем следующее:
         1. Сохраните A[i]-A[j] в переменной, скажем, diff.
         2. Итерируйте от 0 до diff с помощью k и сделайте следующее:
            1. Сохраните в dp[i] максимум между dp[i] и dp[j][k]+1 .
            2. Таким образом, переход:
               1. dp[i]=max(dp[i], dp[j][k]+1)
3. Итерируйте от 0 до MAX , используя i , и сохраните максимальное значение dp[N-1][i] в переменной, скажем, maxSetSize.
4. Ответ будет N-maxSetSize .

Ниже приведен код для реализации подхода

Временная сложность: O(N ² *M), где M — максимальный элемент в A,
Вспомогательное пространство: O(N*M)

Эффективный подход с использованием оптимизированного динамического программирования. В приведенном выше подходе минимум от 0 до diff для каждого k вычисляется повторно. Чтобы избежать этого, можно поддерживать максимальный массив 2D-префиксов pref , где pref[i][j] хранит максимальный размер подмножеств, так что от 1 до i выполняется следующее условие:

1. А[я]-А[я-1]=А[j]

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*M+N ² ), где M — максимальный элемент в A,
Вспомогательное пространство: O(N*M)