Dada una array arr[ ] de N enteros. La tarea es encontrar la longitud máxima del subarreglo contiguo creciente más largo después de eliminar exactamente un elemento del arreglo dado.
Ejemplos:
Entrada: N = 5, arr[] = { 2, 4, 1, 5, 7 }
Salida : 4
Explicación: después de eliminar el tercer elemento de la array, la array arr[ ] se convierte en [2, 4, 5, 7] . por lo tanto, la longitud del subarreglo contiguo creciente más largo es 4, que es el máximo.
Entrada: N = 4, arr[] = { 2, 1, 3, 1 }
Salida: 2
Explicación: podemos eliminar el segundo o el primer elemento de la array, y la array, arr[] se convierte en {1, 3, 1} o {2, 3, 1}, y la longitud del subarreglo contiguo creciente más largo es 2, que es el máximo.
Enfoque: la tarea se puede resolver haciendo un seguimiento de la subsecuencia creciente más larga que comienza en el índice ‘i’ y también termina en el índice ‘i’.
- Cree dos arrays front[ ] y back[ ] de tamaño N e inicialice ambas arrays con 1 .
- Calcule front[i] y back[i] para cada i de 1 a N , donde front[i] representa la longitud máxima de la subsecuencia creciente más larga que comienza en la posición i y back[i] representa la longitud máxima de la subsecuencia creciente más larga que termina en la posición i.
- La array front[ ] se puede calcular en orden de izquierda a derecha con la siguiente condición: if(a[i] > a[i-1]) update front[i] = front[i-1] + 1, else continue . De la misma manera, la array back[ ] se puede calcular en orden de derecha a izquierda con la siguiente condición: if(a[i] < a[i+1]) update back[i] = back[i+1] + 1 , de lo contrario continuar
- Ahora calcule el ans, inicializado con 1, con estas dos arrays.
- Actualice y si (a[i] < a[i+2]), significa que (i+1) el elemento se está eliminando, lo mismo con la array back[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// c++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum length of longest
// increasing contiguous subarray after removing
// exactly one element from array
int maxLenSubarr(int arr[], int n)
{
// Creating front[] and back[] arrays
int front[n], back[n];
for (int i = 0; i < n; i++) {
front[i] = 1;
back[i] = 1;
}
// Calculating the front[]
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i - 1]) {
// Update front[i]
front[i] = front[i - 1] + 1;
}
}
// Calculating the back[]
for (int i = n - 2; i >= 0; i--) {
if (arr[i] < arr[i + 1]) {
// update back[i]
back[i] = back[i + 1] + 1;
}
}
// Store the length of longest increasing
// contiguous subarray
int ans = 1;
// Check whether first element is
// contributing in subarray or not
bool check_first = true;
// Keep track of longest subarray when
// first element is removed
int ans_first = 1;
for (int i = 1; i < n; i++) {
// front[i] == 1 means contribution of
// first element in max
// length subarray has ended
if (front[i] == 1) {
check_first = true;
}
ans_first = max(ans_first, front[i]);
}
// First element contributes in the subarray
if (check_first == false) {
ans_first -= 1;
}
// Check whether last element is
// contributing in subarray or not
bool check_last = true;
// Keep track of longest subarray when
// last element is removed
int ans_last = 1;
for (int i = n - 2; i >= 0; i--) {
// back[i] == 1 means contribution of
// last element in max
// length subarray has ended
if (back[i] == 1) {
check_last = true;
}
ans_last = max(ans_last, back[i]);
}
// Last element contributes in the subarray
if (check_last == false) {
ans_last -= 1;
}
// Update ans
ans = max(ans_first, ans_last);
// Calculating max length when
// (i+1)th element is deleted
for (int i = 0; i < n - 2; i++) {
if (arr[i] < arr[i + 2]) {
ans = max(ans,
front[i] + back[i + 2]);
}
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 2, 1, 3, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxLenSubarr(arr, n);
return 0;
}
Java
// Java program for the above approach
public class GFG {
// Function to find the maximum length of longest
// increasing contiguous subarray after removing
// exactly one element from array
static int maxLenSubarr(int arr[], int n)
{
// Creating front[] and back[] arrays
int front[] = new int[n];
int back[] = new int[n];
for (int i = 0; i < n; i++) {
front[i] = 1;
back[i] = 1;
}
// Calculating the front[]
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i - 1]) {
// Update front[i]
front[i] = front[i - 1] + 1;
}
}
// Calculating the back[]
for (int i = n - 2; i >= 0; i--) {
if (arr[i] < arr[i + 1]) {
// update back[i]
back[i] = back[i + 1] + 1;
}
}
// Store the length of longest increasing
// contiguous subarray
int ans = 1;
// Check whether first element is
// contributing in subarray or not
boolean check_first = true;
// Keep track of longest subarray when
// first element is removed
int ans_first = 1;
for (int i = 1; i < n; i++) {
// front[i] == 1 means contribution of
// first element in max
// length subarray has ended
if (front[i] == 1) {
check_first = true;
}
ans_first = Math.max(ans_first, front[i]);
}
// First element contributes in the subarray
if (check_first == false) {
ans_first -= 1;
}
// Check whether last element is
// contributing in subarray or not
boolean check_last = true;
// Keep track of longest subarray when
// last element is removed
int ans_last = 1;
for (int i = n - 2; i >= 0; i--) {
// back[i] == 1 means contribution of
// last element in max
// length subarray has ended
if (back[i] == 1) {
check_last = true;
}
ans_last = Math.max(ans_last, back[i]);
}
// Last element contributes in the subarray
if (check_last == false) {
ans_last -= 1;
}
// Update ans
ans = Math.max(ans_first, ans_last);
// Calculating max length when
// (i+1)th element is deleted
for (int i = 0; i < n - 2; i++) {
if (arr[i] < arr[i + 2]) {
ans = Math.max(ans,
front[i] + back[i + 2]);
}
}
return ans;
}
// Driver code
public static void main (String[] args) {
int arr[] = { 2, 1, 3, 1 };
int n = arr.length;
System.out.println(maxLenSubarr(arr, n));
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to find the maximum length of longest # increasing contiguous subarray after removing # exactly one element from array def maxLenSubarr(arr, n) : # Creating front[] and back[] arrays front = [0] * n; back = [0] * n; for i in range(n) : front[i] = 1; back[i] = 1; # Calculating the front[] for i in range(1, n) : if (arr[i] > arr[i - 1]) : # Update front[i] front[i] = front[i - 1] + 1; # Calculating the back[] for i in range(n - 2, -1, -1) : if (arr[i] < arr[i + 1]) : # update back[i] back[i] = back[i + 1] + 1; # Store the length of longest increasing # contiguous subarray ans = 1; # Check whether first element is # contributing in subarray or not check_first = True; # Keep track of longest subarray when # first element is removed ans_first = 1; for i in range(1, n) : # front[i] == 1 means contribution of # first element in max # length subarray has ended if (front[i] == 1) : check_first = True; ans_first = max(ans_first, front[i]); # First element contributes in the subarray if (check_first == False) : ans_first -= 1; # Check whether last element is # contributing in subarray or not check_last = True; # Keep track of longest subarray when # last element is removed ans_last = 1; for i in range(n - 2, -1, -1) : # back[i] == 1 means contribution of # last element in max # length subarray has ended if (back[i] == 1) : check_last = True; ans_last = max(ans_last, back[i]); # Last element contributes in the subarray if (check_last == False) : ans_last -= 1; # Update ans ans = max(ans_first, ans_last); # Calculating max length when # (i+1)th element is deleted for i in range( n - 2) : if (arr[i] < arr[i + 2]) : ans = max(ans, front[i] + back[i + 2]); return ans; # Driver code if __name__ == "__main__" : arr = [ 2, 1, 3, 1 ]; n = len(arr); print(maxLenSubarr(arr, n)); # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
public class GFG {
// Function to find the maximum length of longest
// increasing contiguous subarray after removing
// exactly one element from array
static int maxLenSubarr(int []arr, int n)
{
// Creating front[] and back[] arrays
int []front = new int[n];
int []back = new int[n];
for (int i = 0; i < n; i++) {
front[i] = 1;
back[i] = 1;
}
// Calculating the front[]
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i - 1]) {
// Update front[i]
front[i] = front[i - 1] + 1;
}
}
// Calculating the back[]
for (int i = n - 2; i >= 0; i--) {
if (arr[i] < arr[i + 1]) {
// update back[i]
back[i] = back[i + 1] + 1;
}
}
// Store the length of longest increasing
// contiguous subarray
int ans = 1;
// Check whether first element is
// contributing in subarray or not
bool check_first = true;
// Keep track of longest subarray when
// first element is removed
int ans_first = 1;
for (int i = 1; i < n; i++) {
// front[i] == 1 means contribution of
// first element in max
// length subarray has ended
if (front[i] == 1) {
check_first = true;
}
ans_first = Math.Max(ans_first, front[i]);
}
// First element contributes in the subarray
if (check_first == false) {
ans_first -= 1;
}
// Check whether last element is
// contributing in subarray or not
bool check_last = true;
// Keep track of longest subarray when
// last element is removed
int ans_last = 1;
for (int i = n - 2; i >= 0; i--) {
// back[i] == 1 means contribution of
// last element in max
// length subarray has ended
if (back[i] == 1) {
check_last = true;
}
ans_last = Math.Max(ans_last, back[i]);
}
// Last element contributes in the subarray
if (check_last == false) {
ans_last -= 1;
}
// Update ans
ans = Math.Max(ans_first, ans_last);
// Calculating max length when
// (i+1)th element is deleted
for (int i = 0; i < n - 2; i++) {
if (arr[i] < arr[i + 2]) {
ans = Math.Max(ans,
front[i] + back[i + 2]);
}
}
return ans;
}
// Driver code
public static void Main(string[] args) {
int []arr = { 2, 1, 3, 1 };
int n = arr.Length;
Console.WriteLine(maxLenSubarr(arr, n));
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the maximum length of longest
// increasing contiguous subarray after removing
// exactly one element from array
function maxLenSubarr(arr, n)
{
// Creating front[] and back[] arrays
let front = new Array(n), back = new Array(n);
for (let i = 0; i < n; i++) {
front[i] = 1;
back[i] = 1;
}
// Calculating the front[]
for (let i = 1; i < n; i++) {
if (arr[i] > arr[i - 1]) {
// Update front[i]
front[i] = front[i - 1] + 1;
}
}
// Calculating the back[]
for (let i = n - 2; i >= 0; i--) {
if (arr[i] < arr[i + 1]) {
// update back[i]
back[i] = back[i + 1] + 1;
}
}
// Store the length of longest increasing
// contiguous subarray
let ans = 1;
// Check whether first element is
// contributing in subarray or not
let check_first = true;
// Keep track of longest subarray when
// first element is removed
let ans_first = 1;
for (let i = 1; i < n; i++) {
// front[i] == 1 means contribution of
// first element in max
// length subarray has ended
if (front[i] == 1) {
check_first = true;
}
ans_first = Math.max(ans_first, front[i]);
}
// First element contributes in the subarray
if (check_first == false) {
ans_first -= 1;
}
// Check whether last element is
// contributing in subarray or not
let check_last = true;
// Keep track of longest subarray when
// last element is removed
let ans_last = 1;
for (let i = n - 2; i >= 0; i--) {
// back[i] == 1 means contribution of
// last element in max
// length subarray has ended
if (back[i] == 1) {
check_last = true;
}
ans_last = Math.max(ans_last, back[i]);
}
// Last element contributes in the subarray
if (check_last == false) {
ans_last -= 1;
}
// Update ans
ans = Math.max(ans_first, ans_last);
// Calculating max length when
// (i+1)th element is deleted
for (let i = 0; i < n - 2; i++) {
if (arr[i] < arr[i + 2]) {
ans = Math.max(ans,
front[i] + back[i + 2]);
}
}
return ans;
}
// Driver code
let arr = [2, 1, 3, 1];
let n = arr.length
document.write(maxLenSubarr(arr, n));
// This code is contributed by Potta Lokesh
</script>
Producción
2
Complejidad temporal : O(N)
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por subhankarjadab y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA