minimum-number-of-removals-to-make-mountain-array.md

Minimum Number of Removals to Make Mountain Array

Nov 30, 2020 · 3 min read

Mountain Array называется такой массив, что есть ровно один элемент, который делит массив на две части: строго возрастающую и строго убывающую. Получается как бы «пик» между ними.

Я разбирал задачу про поиск «пикового элемента» в таком массиве.

А в этой задаче требуется найти минимальное количество элементов, которое нужно удалить из массива, чтобы оставшийся массив стал Mountain Array.

Задача на LeetCode.

Решение #

Несколько примеров:

[2,1,1,5,6,2,3,1]

Можем удалить элементы с индексами 0,1,5 и получим [1,5,6,3,1] (6 — пик).

[4,3,2,1,1,2,3,1]

Можем удалить первые четыре элемента и получим [1,2,3,1] (3 — пик).

Вместо того, чтобы реально удалять элементы, на эту задачу можно посмотреть немного иначе — что если мы будем искать mountain array максимальной длины?

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

В чем разница между подмассивом (subarray) и подпоследовательностью (subsequence)?

Тогда в качестве ответа можно вернуть разницу между длиной исходного массива и найденного, получим минимальное количество элементов, которое нужно удалить.

Каким образом искать mountain array в массиве среди подпоследовательностей?

В этом поможет хорошо известная задача поиска наибольшей возрастающей подпоследовательности (Longest Increasing Subsequence).

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

Пусть dp[i] — длина наибольшей возрастающей подпоследовательности до i-го элемента. Что важно в дпшечке? Рекуррентное соотношение.

Допустим, нам известно значение dp[i]. Как найти dp[i + 1]?

Все элементы, которые строго меньше i + 1-го (чтобы удовлетворить требованию возрастания), могут быть включены в новую подпоследовательность с i + 1 элементом на конце.

Соответственно, надо пройтись по всем элементам dp до i (т.е. длинам) и найти максимальный — таким образом мы включим i + 1 элемент в наибольшую на данный момент подпоследовательность, а dp[i + 1] будет равен найденный максимум плюс один.

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function LIS(nums) {
  const result = [...Array(nums.length)].fill(1);

  for (let i = 1; i < nums.length; i++) {
    // для каждого элемента проходимся по всем dp[j], j = 0..i
    // т.е. смотрим на все длины ДО,
    // чтобы найти максимальное значение
    for (let j = 0; j < i; j++) {
      // убеждаемся, что находимся
      // внутри возрастающей подпоследовательности
      if (nums[i] > nums[j]) {
        result[i] = Math.max(result[j] + 1, result[i]);
      }
    }
  }
  return result;
}

Сложность данного решения — O(n^2), где n - длина исходного массива.

Каким образом это поможет в решении исходной задачи? Мы можем найти LIS слева направо и справа налево, получив таким образом наибольшие длины возрастающей и убывающей (справа налево) подпоследовательностей.

Теперь для каждого элемента мы можем сказать наибольшие длины подпоследовательностей возрастающей до и убывающей после данного элемента, а это как раз и есть «пики» нужных нам mountain array.

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumMountainRemovals = function(nums) {
  // находим длины наибольших
  // возрастающей и убывающей подпоследовательностей
  const leftLIS = LIS(nums);
  const rightLIS = LIS(nums.reverse()).reverse();

  let result = 0;
  // проверяем все «пики»
  // и ищем максимальную длину
  for (let i = 1; i < nums.length - 1; i++) {
    // длины должны быть больше 1
    // чтобы i-й элемент был валидным «пиком»
    if (leftLIS[i] > 1 && rightLIS[i] > 1) {
      // -1 чтобы не включать центральный элемент дважды
      result = Math.max(result, leftLIS[i] + rightLIS[i] - 1);
    }
  }
  // остаётся вычесть максимальную длину из исходной,
  // чтобы получить минимальное количество удалений
  return nums.length - result;
};

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function LIS(nums) {
  const result = [...Array(nums.length)].fill(1);

  for (let i = 1; i < nums.length; i++) {
    // для каждого элемента проходимся по всем dp[j], j = 0..i
    // т.е. смотрим на все длины ДО,
    // чтобы найти максимальное значение
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        result[i] = Math.max(result[j] + 1, result[i]);
      }
    }
  }
  return result;
}

PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

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