En este artículo, discutiremos una solución eficiente para el problema ‘Minimum Number of Removals to Make Mountain Array’, utilizando programación dinámica en Java.
Descripción del Problema
Un array es considerado un mountain array si cumple con las siguientes condiciones:- El array tiene una longitud de al menos 3 elementos.
- Existe un índice i (0-indexado) tal que 0 < i < arr.length – 1, donde:
arr[0] < arr[1] < ... < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]
Solución en Java
La solución se puede abordar usando conceptos de programación dinámica para determinar la subsecuencia creciente y decreciente más larga formando un mountain. Te mostramos a continuación el código Java para resolver este problema:
public class MountainArray {
public int minimumMountainRemovals(int[] nums) {
int n = nums.length;
int[] lis = new int[n]; // Longest Increasing Subsequence
int[] lds = new int[n]; // Longest Decreasing Subsequence
// Calculate LIS for each element
for (int i = 0; i < n; i++) {
lis[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
lis[i] = Math.max(lis[i], lis[j] + 1);
}
}
}
// Calculate LDS for each element
for (int i = n - 1; i >= 0; i--) {
lds[i] = 1;
for (int j = n - 1; j > i; j--) {
if (nums[j] < nums[i]) {
lds[i] = Math.max(lds[i], lds[j] + 1);
}
}
}
int maxMountainLength = 0;
// Find the maximum mountain length
for (int i = 1; i < n - 1; i++) {
if (lis[i] > 1 && lds[i] > 1) { // element must be a peak
maxMountainLength = Math.max(maxMountainLength, lis[i] + lds[i] - 1);
}
}
// Minimum removals to make mountain array
return n - maxMountainLength;
}
}