Минимизируйте сумму пары, которая при удалении делит массив на 3 подмассива

Опубликовано: 21 Сентября, 2022

Учитывая массив arr размера N , задача состоит в том, чтобы найти пару элементов с минимальной суммой, которая при удалении разбивает массив на 3 непустых подмассива исходного массива. Выведите сумму элементов этой пары.

Input: arr[]: {4, 2, 1, 2, 4}
Output: 4
Explanation:
Minimum sum pairs are values (2, 1) and (1, 2) but selecting a pair with adjacent indices won’t break the array into 3 parts. Next minimum value pair is (2, 2), which divides the array into {4}, {1}, {4}. Hence the answer is 2 + 2 = 4.

Input: arr[] = {5, 2, 4, 6, 3, 7}
Output: 5
Explanation:
Among all the pairs which break the array into 3 subparts, pair with values (2, 3) gives minimum sum.

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

  • ни одна из конечных точек (индекс 0 и N-1 ) не может быть выбрана.
  • соседние индексы не могут быть выбраны.

Итак, найдите все комбинации возможных пар и выберите ту, которая соответствует вышеуказанным условиям и имеет наименьшую сумму из всех.

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

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

  1. Создайте массив prefixMin, в котором i -й элемент представляет минимальный элемент с 0-го по i-й индекс в массиве arr.
  2. Создайте переменную ans для хранения окончательного ответа и инициализируйте ее значением INT_MAX.
  3. Теперь запустите цикл для i=3 до i=N-1 (начиная с 3, поскольку 0-й не может быть выбран, и этот цикл предназначен для выбора второго элемента пары, что означает, что его даже нельзя запустить с 2 потому что тогда единственными оставшимися параметрами для первого элемента являются 1 и 2, которые не соответствуют заданным условиям) и на каждой итерации изменяют ans на минимальное значение из ans и arr[i]+prefixMin[i-2] .
  4. Распечатайте ответ после выполнения вышеуказанных шагов.

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


Временная сложность : O(n)

Космическая сложность : O(n)

РЕКОМЕНДУЕМЫЕ СТАТЬИ