Удалите минимальное количество элементов с любой стороны, чтобы 2 * min стало больше, чем max

01.01.2020Динамическое программирование, Массивы

Если задан несортированный массив, обрежьте массив так, чтобы минимум в два раза был больше максимума в обрезанном массиве. Элементы должны быть удалены с любого конца массива.

Количество удалений должно быть минимальным.

Примеры:

arr[] = {4, 5, 100, 9, 10, 11, 12, 15, 200}
Output: 4
We need to remove 4 elements (4, 5, 100, 200)
so that 2*min becomes more than max.


arr[] = {4, 7, 5, 6}
Output: 0
We don't need to remove any element as 
4*2 > 7 (Note that min = 4, max = 8)

arr[] = {20, 7, 5, 6}
Output: 1
We need to remove 20 so that 2*min becomes
more than max

arr[] = {20, 4, 1, 3}
Output: 3
We need to remove any three elements from ends
like 20, 4, 1 or 4, 1, 3 or 20, 3, 1 or 20, 4, 1

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

Наивное решение:
Наивное решение состоит в том, чтобы попробовать каждый возможный случай, используя повторение. Ниже приведен наивный рекурсивный алгоритм. Обратите внимание, что алгоритм возвращает только минимальное количество удалений, которые он должен сделать, он не печатает урезанный массив. Его можно легко модифицировать для печати обрезанного массива.

// Returns minimum number of removals to be made in
// arr[l..h]
minRemovals(int arr[], int l, int h)
1) Find min and max in arr[l..h]
2) If 2*min > max, then return 0.
3) Else return minimum of "minRemovals(arr, l+1, h) + 1"
   and "minRemovals(arr, l, h-1) + 1"

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

C ++

// C ++ реализация вышеуказанного подхода
#include <iostream>

using namespace std;

// Полезная функция для поиска минимум двух чисел

int min(int a, int b) {return (a < b)? a : b;}

// Полезная функция для поиска минимума в arr [l..h]

int min(int arr[], int l, int h)

{

int mn = arr[l];

for (int i=l+1; i<=h; i++)

if (mn > arr[i])

mn = arr[i];

return mn;

}

// Полезная функция для поиска максимума в arr [l..h]

int max(int arr[], int l, int h)

{

int mx = arr[l];

for (int i=l+1; i<=h; i++)

if (mx < arr[i])

mx = arr[i];

return mx;

}

// Возвращает минимальное количество удалений с любого конца
// в arr [l..h], так что 2 * min становится больше, чем max.

int minRemovals(int arr[], int l, int h)

{

// Если есть 1 или меньше элементов, вернуть 0

// Для одного элемента 2 * min> max

// (Предположение: все элементы положительны в arr [])

if (l >= h) return 0;

// 1) Найти минимум и максимум в arr [l..h]

int mn = min(arr, l, h);

int mx = max(arr, l, h);

// Если соблюдается свойство, удаление не требуется

if (2*mn > mx)

return 0;

// В противном случае удаляем символ из левого конца и повторяем,

// затем удаляем символ с правого конца и повторяем

// возвращается минимум два

return min(minRemovals(arr, l+1, h),

minRemovals(arr, l, h-1)) + 1;

}

// Программа драйвера для проверки вышеуказанных функций

int main()

{

int arr[] = {4, 5, 100, 9, 10, 11, 12, 15, 200};

int n = sizeof(arr)/sizeof(arr[0]);

cout << minRemovals(arr, 0, n-1);

return 0;

}

Джава

// Java реализация вышеуказанного подхода

class GFG

{
// Полезная функция для поиска минимум двух чисел

static int min(int a, int b) {return (a < b)? a : b;}

// Полезная функция для поиска минимума в arr [l..h]

static int min(int arr[], int l, int h)

{

int mn = arr[l];

for (int i=l+1; i<=h; i++)

if (mn > arr[i])

mn = arr[i];

return mn;

}

// Полезная функция для поиска максимума в arr [l..h]

static int max(int arr[], int l, int h)

{

int mx = arr[l];

for (int i=l+1; i<=h; i++)

if (mx < arr[i])

mx = arr[i];

return mx;

}

static int minRemovals(int arr[], int l, int h)

{

// Если есть 1 или меньше элементов, вернуть 0

// Для одного элемента 2 * min> max

// (Предположение: все элементы положительны в arr [])

if (l >= h) return 0;

// 1) Найти минимум и максимум в arr [l..h]

int mn = min(arr, l, h);

int mx = max(arr, l, h);

// Если соблюдается свойство, удаление не требуется

if (2*mn > mx)

return 0;

// В противном случае удаляем символ из левого конца и повторяем,

// затем удаляем символ с правого конца и повторяем

// возвращается минимум два

return min(minRemovals(arr, l+1, h),

minRemovals(arr, l, h-1)) + 1;

}

// Код драйвера

public static void main(String[] args)

{

int arr[] = {4, 5, 100, 9, 10, 11, 12, 15, 200};

int n = arr.length;

System.out.print(minRemovals(arr, 0, n-1));

}
}

// Этот код предоставлен Мукулом Сингхом.

python3

# Python3 реализация вышеуказанного подхода
# Полезная функция для поиска
# минимум в обр [л..ч]

def mini(arr, l, h):

mn = arr[l]

for i in range(l + 1, h + 1):

if (mn > arr[i]):

mn = arr[i]

return mn

# Полезная функция для поиска
# максимум в обр [л..ч]

def max(arr, l, h):

mx = arr[l]

for i in range(l + 1, h + 1):

if (mx < arr[i]):

mx = arr[i]

return mx

# Возвращает минимальное количество
# удаления с любого конца в
# arr [l..h], так что 2 * min становится
# больше макс.

def minRemovals(arr, l, h):

# Если есть 1 или меньше элементов, вернуть 0

# Для одного элемента 2 * min> max

# (Предположение: все элементы положительны в arr [])

if (l >= h):

return 0

# 1) Найти минимум и максимум

# в обр [л..ч]

mn = mini(arr, l, h)

mx = max(arr, l, h)

# Если свойство соблюдается,

# удаление не требуется

if (2 * mn > mx):

return 0

# В противном случае удалите символ из

# левый конец и повторить, затем удалить

# символ с правого конца и повторения,

# взять минимум два возвращается

return (min(minRemovals(arr, l + 1, h),

minRemovals(arr, l, h - 1)) + 1)

Код водителя

arr = [4, 5, 100, 9, 10,

11, 12, 15, 200]

n = len(arr)

print(minRemovals(arr, 0, n - 1))

# Этот код добавлен
# от sahilshelangia

C #

// C # реализация вышеуказанного подхода

using System;

class GFG

{
// Полезная функция для поиска минимум двух чисел

static int min(int a, int b) {return (a < b)? a : b;}

// Полезная функция для поиска минимума в arr [l..h]

static int min(int[] arr, int l, int h)

{

int mn = arr[l];

for (int i=l+1; i<=h; i++)

if (mn > arr[i])

mn = arr[i];

return mn;

}

// Полезная функция для поиска максимума в arr [l..h]

static int max(int[] arr, int l, int h)

{

int mx = arr[l];

for (int i=l+1; i<=h; i++)

if (mx < arr[i])

mx = arr[i];

return mx;

}

static int minRemovals(int[] arr, int l, int h)

{

// Если есть 1 или меньше элементов, вернуть 0

// Для одного элемента 2 * min> max

// (Предположение: все элементы положительны в arr [])

if (l >= h) return 0;

// 1) Найти минимум и максимум в arr [l..h]

int mn = min(arr, l, h);

int mx = max(arr, l, h);

// Если соблюдается свойство, удаление не требуется

if (2*mn > mx)

return 0;

// В противном случае удаляем символ из левого конца и повторяем,

// затем удаляем символ с правого конца и повторяем

// возвращается минимум два

return min(minRemovals(arr, l+1, h),

minRemovals(arr, l, h-1)) + 1;

}

// Код драйвера

public static void Main()

{

int[] arr = {4, 5, 100, 9, 10, 11, 12, 15, 200};

int n = arr.Length;

Console.Write(minRemovals(arr, 0, n-1));
}
}

// Этот код предоставлен Akanksha Rai

PHP

<?php
// PHP реализация вышеупомянутого подхода

// Полезная функция для поиска
// минимум в обр [л..ч]

function min_1(&$arr, $l, $h)

{

$mn = $arr[$l];

for ($i = $l + 1; $i <= $h; $i++)

if ($mn > $arr[$i])

$mn = $arr[$i];

return $mn;

}

// Полезная функция для поиска
// максимум в обр [л..ч]

function max_1(&$arr, $l, $h)

{

$mx = $arr[$l];

for ($i = $l + 1; $i <= $h; $i++)

if ($mx < $arr[$i])

$mx = $arr[$i];

return $mx;

}

// Возвращает минимальное количество удалений
// с любого конца в arr [l..h], чтобы
// 2 * мин становится больше макс.

function minRemovals(&$arr, $l, $h)

{

// Если есть 1 или меньше элементов,

// возвращаем 0. Для одного элемента

// 2 * мин> макс. (Предположение: все

// элементы положительны в arr [])

if ($l >= $h) return 0;

// 1) Найти минимум и максимум в arr [l..h]

$mn = min_1($arr, $l, $h);

$mx = max_1($arr, $l, $h);

// Если свойство соблюдается,

// удаление не требуется

if (2 * $mn > $mx)

return 0;

// В противном случае удалить символ слева

// закончить и повторить, затем удалить символ

// с правого конца и повторить, взять

// возвращается минимум два

return min(minRemovals($arr, $l + 1, $h),

minRemovals($arr, $l, $h - 1)) + 1;

}

// Код драйвера

$arr = array(4, 5, 100, 9, 10,

11, 12, 15, 200);

$n = sizeof($arr);

echo minRemovals($arr, 0, $n - 1);

// Этот код добавлен
// ChitraNayal
?>

Выход:

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

  T(n) = 2T(n-1) + O(n)

Верхняя граница для решения вышеупомянутого повторения была бы O (nx 2 ⁿ ).

Динамическое программирование:
Вышеупомянутый рекурсивный код имеет много перекрывающихся подзадач. Например, minRemovals (arr, l + 1, h-1) оценивается дважды. Таким образом, динамическое программирование — это выбор для оптимизации решения. Ниже приводится решение на основе динамического программирования.

C ++

// C ++ программа вышеуказанного подхода
#include <iostream>

using namespace std;

// Полезная функция для поиска минимум двух чисел

int min(int a, int b) {return (a < b)? a : b;}

// Полезная функция для поиска минимума в arr [l..h]

int min(int arr[], int l, int h)

{

int mn = arr[l];

for (int i=l+1; i<=h; i++)

if (mn > arr[i])

mn = arr[i];

return mn;

}

// Полезная функция для поиска максимума в arr [l..h]

int max(int arr[], int l, int h)

{

int mx = arr[l];

for (int i=l+1; i<=h; i++)

if (mx < arr[i])

mx = arr[i];

return mx;

}

int minRemovalsDP(int arr[], int n)

{

// Создать таблицу для хранения решений подзадач

int table[n][n], gap, i, j, mn, mx;

// Заполнить таблицу, используя приведенную выше рекурсивную формулу. Обратите внимание, что таблица

// заполнен по диагонали (аналог http://goo.gl/PQqoS ),

// из диагональных элементов в таблицу [0] [n-1], что является результатом.

for (gap = 0; gap < n; ++gap)

{

for (i = 0, j = gap; j < n; ++i, ++j)

{

mn = min(arr, i, j);

mx = max(arr, i, j);

table[i][j] = (2*mn > mx)? 0: min(table[i][j-1]+1,

table[i+1][j]+1);

}

return table[0][n-1];

}

// Программа драйвера для проверки вышеуказанных функций

int main()

{

int arr[] = {20, 4, 1, 3};

int n = sizeof(arr)/sizeof(arr[0]);

cout << minRemovalsDP(arr, n);

return 0;

}

Джава

// Java-программа вышеуказанного подхода

class GFG {

// Полезная функция для поиска минимум двух чисел

static int min(int a, int b) {

return (a < b) ? a : b;

}

// Полезная функция для поиска минимума в arr [l..h]

static int min(int arr[], int l, int h) {

int mn = arr[l];

for (int i = l + 1; i <= h; i++) {

if (mn > arr[i]) {

mn = arr[i];

}

return mn;

}

// Полезная функция для поиска максимума в arr [l..h]

static int max(int arr[], int l, int h) {

int mx = arr[l];

for (int i = l + 1; i <= h; i++) {

if (mx < arr[i]) {

mx = arr[i];

}

return mx;

}

static int minRemovalsDP(int arr[], int n) {

// Создать таблицу для хранения решений подзадач

int table[][] = new int[n][n], gap, i, j, mn, mx;

// Заполнить таблицу, используя приведенную выше рекурсивную формулу. Обратите внимание, что таблица

// заполнен по диагонали (аналог http://goo.gl/PQqoS ),

// из диагональных элементов в таблицу [0] [n-1], что является результатом.

for (gap = 0; gap < n; ++gap) {

for (i = 0, j = gap; j < n; ++i, ++j) {

mn = min(arr, i, j);

mx = max(arr, i, j);

table[i][j] = (2 * mn > mx) ? 0 : min(table[i][j - 1] + 1,

table[i + 1][j] + 1);

}

return table[0][n - 1];

}

// Программа драйвера для проверки вышеуказанных функций

public static void main(String[] args) {

int arr[] = {20, 4, 1, 3};

int n = arr.length;

System.out.println(minRemovalsDP(arr, n));

}

}
// Этот код предоставлен 29AJayKumar

python3

# Python3 программа вышеуказанного подхода

# Полезная функция для поиска
# минимум в обр [л..ч]

def min1(arr, l, h):

mn = arr[l];

for i in range(l + 1,h+1):

if (mn > arr[i]):

mn = arr[i];

return mn;

# Полезная функция для поиска
# максимум в обр [л..ч]

def max1(arr, l, h):

mx = arr[l];

for i in range(l + 1, h + 1):

if (mx < arr[i]):

mx = arr[i];

return mx;

# Возвращает минимальное количество удалений
# с любого конца в arr [l..h], так что
# 2 * мин становится больше, чем макс.

def minRemovalsDP(arr, n):

# Создать таблицу для хранения

# решения подзадач

table = [[0 for x in range(n)] for y in range(n)];

# Заполните таблицу, используя приведенную выше рекурсивную формулу.

# Обратите внимание, что таблица заполнена по диагонали

# (аналог http: # goo.gl / PQqoS) из диагональных элементов

# в таблицу [0] [n-1], что является результатом.

for gap in range(n):

i = 0;

for j in range(gap,n):

mn = min1(arr, i, j);

mx = max1(arr, i, j);

table[i][j] = 0 if (2 * mn > mx) else min(table[i][j - 1] + 1,table[i + 1][j] + 1);

i += 1;

return table[0][n - 1];

Код водителя

arr = [20, 4, 1, 3];

n = len(arr);

print(minRemovalsDP(arr, n));

# Этот код предоставлен mits

C #

// C # программа вышеуказанного подхода

using System;

public class GFG {

// Полезная функция для поиска минимум двух чисел

static int min(int a, int b) {

return (a < b) ? a : b;

}

// Полезная функция для поиска минимума в arr [l..h]

static int min(int []arr, int l, int h) {

int mn = arr[l];

for (int i = l + 1; i <= h; i++) {

if (mn > arr[i]) {

mn = arr[i];

}

return mn;

}

// Полезная функция для поиска максимума в arr [l..h]

static int max(int []arr, int l, int h) {

int mx = arr[l];

for (int i = l + 1; i <= h; i++) {

if (mx < arr[i]) {

mx = arr[i];

}

return mx;

}

// Возвращает минимальное количество удалений с любого конца

// в arr [l..h], так что 2 * min становится больше, чем max.

static int minRemovalsDP(int []arr, int n) {

// Создать таблицу для хранения решений подзадач

int [,]table = new int[n,n];

int gap, i, j, mn, mx;

// Заполнить таблицу, используя приведенную выше рекурсивную формулу. Обратите внимание, что таблица

// заполнен по диагонали (аналог http://goo.gl/PQqoS ),

// из диагональных элементов в таблицу [0] [n-1], что является результатом.

for (gap = 0; gap < n; ++gap) {

for (i = 0, j = gap; j < n; ++i, ++j) {

mn = min(arr, i, j);

mx = max(arr, i, j);

table[i,j] = (2 * mn > mx) ? 0 : min(table[i,j - 1] + 1,

table[i + 1,j] + 1);

}

return table[0,n - 1];

}

// Программа драйвера для проверки вышеуказанных функций

public static void Main() {

int []arr = {20, 4, 1, 3};

int n = arr.Length;

Console.WriteLine(minRemovalsDP(arr, n));

}

}
// Этот код предоставлен 29AJayKumar

PHP

<?php
// PHP программа вышеуказанного подхода

// Полезная функция для поиска
// минимум в обр [л..ч]

function min1($arr, $l, $h)

{

$mn = $arr[$l];

for ($i = $l + 1; $i <= $h; $i++)

if ($mn > $arr[$i])

$mn = $arr[$i];

return $mn;

}

// Полезная функция для поиска
// максимум в обр [л..ч]

function max1($arr, $l, $h)

{

$mx = $arr[$l];

for ($i = $l + 1; $i <= $h; $i++)

if ($mx < $arr[$i])

$mx = $arr[$i];

return $mx;

}

function minRemovalsDP($arr, $n)

{

// Создать таблицу для хранения

// решения подзадач

$table = array_fill(0, $n,

array_fill(0, $n, 0));

// Заполнить таблицу, используя приведенную выше рекурсивную формулу.

// Обратите внимание, что таблица заполнена по диагонали

// (аналог http://goo.gl/PQqoS ) из диагональных элементов

// к таблице [0] [n-1], которая является результатом.

for ($gap = 0; $gap < $n; ++$gap)

{

for ($i = 0, $j = $gap; $j < $n; ++$i, ++$j)

{

$mn = min1($arr, $i, $j);

$mx = max1($arr, $i, $j);

$table[$i][$j] = (2 * $mn > $mx) ? 0 :

min($table[$i][$j - 1] + 1,

$table[$i + 1][$j] + 1);

}

return $table[0][$n - 1];

}

// Код драйвера

$arr = array(20, 4, 1, 3);

$n = count($arr);

echo minRemovalsDP($arr, $n);

// Этот код предоставлен mits
?>

Выход:

Сложность времени: O (n ³ ), где n — количество элементов в arr [].

Дальнейшая оптимизация:
Приведенный выше код может быть оптимизирован многими способами.
1) Мы можем избежать вычисления min () и / или max (), когда min и / или max не изменены, удалив угловые элементы.

2) Мы можем предварительно обработать массив и построить дерево сегментов за O (n) раз. После построения дерева сегментов мы можем запросить минимальный и максимальный диапазон за время O (Logn). Общая сложность времени уменьшается до O (n ² Logn) времени.

AO (n ^ 2) Решение
Идея состоит в том, чтобы найти подмассив максимального размера, такой что 2 * min> max. Мы запускаем два вложенных цикла, внешний цикл выбирает начальную точку, а внутренний цикл выбирает конечную точку для текущей начальной точки. Мы отслеживаем самый длинный подмассив с данным свойством.

Ниже приводится реализация вышеуказанного подхода. Спасибо Ричарду Чжану за предложение этого решения.

C ++

// AO (n * n) решение, чтобы найти минимум элементов для
// удалить
#include <iostream>
#include <climits>

using namespace std;

int minRemovalsDP(int arr[], int n)

{

// Инициализируем начальный и конечный индексы максимума

// размерный массив со свойством 2 * min> max

int longest_start = -1, longest_end = 0;

// Выбираем разные элементы в качестве отправной точки

for (int start=0; start<n; start++)

{

// Инициализируем минимальное и максимальное значения для текущего запуска

int min = INT_MAX, max = INT_MIN;

// Выбираем разные конечные точки для текущего старта

for (int end = start; end < n; end ++)

{

// Обновление мин и макс при необходимости

int val = arr[end];

if (val < min) min = val;

if (val > max) max = val;

// Если свойство нарушено, то нет

// указать продолжение для большего массива

if (2 * min <= max) break;

// Обновляем longest_start и longest_end при необходимости

if (end - start > longest_end - longest_start ||

longest_start == -1)

{

longest_start = start;

longest_end = end;

}

// Если за свойством нет ни одного элемента,

// затем возвращаем n

if (longest_start == -1) return n;

// Возвращаем количество удаляемых элементов

return (n - (longest_end - longest_start + 1));

}

// Программа драйвера для проверки вышеуказанных функций

int main()

{

int arr[] = {4, 5, 100, 9, 10, 11, 12, 15, 200};

int n = sizeof(arr)/sizeof(arr[0]);

cout << minRemovalsDP(arr, n);

return 0;

}

Джава

// AO (n * n) решение, чтобы найти минимум элементов для
// удалить

class GFG {

static int minRemovalsDP(int arr[], int n) {

// Инициализируем начальный и конечный индексы максимума

// размерный массив со свойством 2 * min> max

int longest_start = -1, longest_end = 0;

// Выбираем разные элементы в качестве отправной точки

for (int start = 0; start < n; start++) {

// Инициализируем минимальное и максимальное значения для текущего запуска

int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;

// Выбираем разные конечные точки для текущего старта

for (int end = start; end < n; end++) {

// Обновление мин и макс при необходимости

int val = arr[end];

if (val < min) {

min = val;

}

if (val > max) {

max = val;

}

// Если свойство нарушено, то нет

// указать продолжение для большего массива

if (2 * min <= max) {

break;

}

// Обновляем longest_start и longest_end при необходимости

if (end - start > longest_end - longest_start

|| longest_start == -1) {

longest_start = start;

longest_end = end;

}

// Если за свойством нет ни одного элемента,

// затем возвращаем n

if (longest_start == -1) {

return n;

}

// Возвращаем количество удаляемых элементов

return (n - (longest_end - longest_start + 1));

}

// Программа драйвера для проверки вышеуказанных функций

public static void main(String[] args) {

int arr[] = {4, 5, 100, 9, 10, 11, 12, 15, 200};

int n = arr.length;

System.out.println(minRemovalsDP(arr, n));

}

// Этот код предоставлен PrinciRaj1992

python3

# AO (n * n) решение, чтобы найти минимум
# элементы для удаления

import sys;

def minRemovalsDP(arr, n):

# Инициализировать начальный и конечный индексы

# подмассива максимального размера

# со свойством 2 * мин> макс

longest_start = -1;

longest_end = 0;

# Выберите разные элементы в качестве отправной точки

for start in range(n):

# Инициализировать мин и макс

# для текущего старта

min = sys.maxsize;

max = -sys.maxsize;

# Выберите разные конечные точки для текущего старта

for end in range(start,n):

# Обновите мин и макс при необходимости

val = arr[end];

if (val < min):

min = val;

if (val > max):

max = val;

# Если свойство нарушено, то нет

# указать, чтобы продолжить для большего массива

if (2 * min <= max):

break;

# Обновите longest_start и longest_end, если необходимо

if (end - start > longest_end - longest_start or longest_start == -1):

longest_start = start;

longest_end = end;

# Если хотя бы один элемент не следит за свойством,

# тогда верните n

if (longest_start == -1):

return n;

# Вернуть количество элементов, которые будут удалены

return (n - (longest_end - longest_start + 1));

Код водителя

arr = [4, 5, 100, 9, 10, 11, 12, 15, 200];

n = len(arr);

print(minRemovalsDP(arr, n));

# Этот код предоставлен mits

C #

// AO (n * n) решение, чтобы найти минимум элементов для
// удалить

using System;

public class GFG {

static int minRemovalsDP(int []arr, int n) {

// Инициализируем начальный и конечный индексы максимума

// размерный массив со свойством 2 * min> max

int longest_start = -1, longest_end = 0;

// Выбираем разные элементы в качестве отправной точки

for (int start = 0; start < n; start++) {

// Инициализируем минимальное и максимальное значения для текущего запуска

int min = int.MaxValue, max = int.MinValue;

// Выбираем разные конечные точки для текущего старта

for (int end = start; end < n; end++) {

// Обновление мин и макс при необходимости

int val = arr[end];

if (val < min) {

min = val;

}

if (val > max) {

max = val;

}

// Если свойство нарушено, то нет

// указать продолжение для большего массива

if (2 * min <= max) {

break;

}

// Обновляем longest_start и longest_end при необходимости

if (end - start > longest_end - longest_start

|| longest_start == -1) {

longest_start = start;

longest_end = end;

}

// Если за свойством нет ни одного элемента,

// затем возвращаем n

if (longest_start == -1) {

return n;

}

// Возвращаем количество удаляемых элементов

return (n - (longest_end - longest_start + 1));

}

// Программа драйвера для проверки вышеуказанных функций

public static void Main() {

int []arr = {4, 5, 100, 9, 10, 11, 12, 15, 200};

int n = arr.Length;

Console.WriteLine(minRemovalsDP(arr, n));

}

// Этот код предоставлен Rajput-Ji

PHP

<?php
// AO (n * n) решение, чтобы найти минимум
// элементы, которые будут удалены

function minRemovalsDP($arr, $n)

{

// Инициализировать начальный и конечный индексы

// подмассива максимального размера

// со свойством 2 * min> max

$longest_start = -1;

$longest_end = 0;

// Выбираем разные элементы в качестве отправной точки

for ($start = 0; $start < $n; $start++)

{

// Инициализировать мин и макс

// для текущего старта

$min = PHP_INT_MAX;

$max = PHP_INT_MIN;

// Выбираем разные конечные точки для текущего старта

for ($end = $start; $end < $n; $end ++)

{

// Обновление мин и макс при необходимости

$val = $arr[$end];

if ($val < $min) $min = $val;

if ($val > $max) $max = $val;

// Если свойство нарушено, то нет

// указать продолжение для большего массива

if (2 * $min <= $max) break;

// Обновляем longest_start и longest_end при необходимости

if ($end - $start > $longest_end - $longest_start ||

$longest_start == -1)

{

$longest_start = $start;

$longest_end = $end;

}

// Если за свойством нет ни одного элемента,

// затем возвращаем n

if ($longest_start == -1) return $n;

// Возвращаем количество удаляемых элементов

return ($n - ($longest_end - $longest_start + 1));

}

// Код драйвера

$arr = array(4, 5, 100, 9, 10, 11, 12, 15, 200);

$n = sizeof($arr);

echo minRemovalsDP($arr, $n);

// Этот код предоставлен jit_t
?>

Выход:

Эта статья пополняемая Рахул Джейна. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Удалите минимальное количество элементов с любой стороны, чтобы 2 * min стало больше, чем max

0.00 (0%) 0 votes