Secuencia decreciente contigua máxima obtenida al eliminar cualquier elemento

Dada una array arr[] de N enteros. La tarea es encontrar la longitud de la secuencia contigua estrictamente decreciente que se puede derivar después de eliminar como máximo un elemento de la array arr [] . 
Ejemplos 
 

Entrada: arr[] = {8, 7, 3, 5, 2, 9} 
Salida: 4 
Explicación: 
Si eliminamos 3, la longitud máxima de la secuencia decreciente es 4 y la secuencia es { 8, 7, 5, 2 } 
Si eliminamos 5, la longitud máxima de la secuencia decreciente es 4 y la secuencia es { 8, 7, 3, 2 } 
En ambas eliminaciones obtenemos 4 como la longitud máxima.
Entrada: arr[] = {1, 2, 9, 8, 3, 7, 6, 4} 
Salida: 5 
 

Acercarse: 
 

• Cree dos arrays, left[] que almacena la longitud de la secuencia decreciente de izquierda a derecha y right[] que almacena la longitud de la secuencia decreciente de derecha a izquierda.
• Recorre la array dada arr[] .
• Si el elemento anterior ( arr[i-1] ) es mayor que el siguiente elemento ( arr[i+1] ), compruebe si eliminar ese elemento dará la longitud máxima de la subsecuencia decreciente o no.
• Actualice la longitud máxima de la subsecuencia decreciente.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find maximum length
// of decreasing sequence by removing
// at most one element
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum length
int maxLength(int* a, int n)
{
    // Initialise maximum length to 1
    int maximum = 1;
 
    // Initialise left[] to find the
    // length of decreasing sequence
    // from left to right
    int left[n];
 
    // Initialise right[] to find the
    // length of decreasing sequence
    // from right to left
    int right[n];
 
    // Initially store 1 at each index of
    // left and right array
    for (int i = 0; i < n; i++) {
        left[i] = 1;
        right[i] = 1;
    }
 
    // Iterate over the array arr[] to
    // store length of decreasing
    // sequence that can be obtained
    // at every index in the right array
    for (int i = n - 2; i >= 0; i--) {
 
        if (a[i] > a[i + 1]) {
            right[i] = right[i + 1] + 1;
        }
 
        // Store the length of longest
        // continuous decreasing
        // sequence in maximum
        maximum = max(maximum, right[i]);
    }
 
    // Iterate over the array arr[] to
    // store length of decreasing
    // sequence that can be obtained
    // at every index in the left array
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            left[i] = left[i - 1] + 1;
        }
    }
 
    if (n > 2) {
        // Check if we can obtain a
        // longer decreasing sequence
        // after removal of any element
        // from the array arr[] with
        // the help of left[] & right[]
        for (int i = 1; i < n - 1; i++) {
            if (a[i - 1] > a[i + 1]) {
                maximum = max(maximum,
                              left[i - 1] + right[i + 1]);
            }
        }
    }
 
    // Return maximum length of sequence
    return maximum;
}
 
// Driver code
int main()
{
    int arr[6] = { 8, 7, 3, 5, 2, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function calling
    cout << maxLength(arr, n) << endl;
    return 0;
}

// Java program to find maximum length
// of decreasing sequence by removing
// at most one element
class GFG {
     
    // Function to find the maximum length
    static int maxLength(int []a, int n)
    {
        // Initialise maximum length to 1
        int maximum = 1;
     
        // Initialise left[] to find the
        // length of decreasing sequence
        // from left to right
        int left [] = new int[n];
     
        // Initialise right[] to find the
        // length of decreasing sequence
        // from right to left
        int right[] = new int[n];
     
        // Initially store 1 at each index of
        // left and right array
        for (int i = 0; i < n; i++) {
            left[i] = 1;
            right[i] = 1;
        }
     
        // Iterate over the array arr[] to
        // store length of decreasing
        // sequence that can be obtained
        // at every index in the right array
        for (int i = n - 2; i >= 0; i--) {
     
            if (a[i] > a[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
     
            // Store the length of longest
            // continuous decreasing
            // sequence in maximum
            maximum = Math.max(maximum, right[i]);
        }
     
        // Iterate over the array arr[] to
        // store length of decreasing
        // sequence that can be obtained
        // at every index in the left array
        for (int i = 1; i < n; i++) {
            if (a[i] < a[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
     
        if (n > 2) {
            // Check if we can obtain a
            // longer decreasing sequence
            // after removal of any element
            // from the array arr[] with
            // the help of left[] & right[]
            for (int i = 1; i < n - 1; i++) {
                if (a[i - 1] > a[i + 1]) {
                    maximum = Math.max(maximum, left[i - 1] + right[i + 1]);
                }
            }
        }
     
        // Return maximum length of sequence
        return maximum;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int arr[] = { 8, 7, 3, 5, 2, 9 };
        int n = arr.length;
     
        // Function calling
        System.out.println(maxLength(arr, n));
    }  
}
 
// This code is contributed by AnkitRai01

# Python3 program to find maximum length
# of decreasing sequence by removing
# at most one element
 
# Function to find the maximum length
def maxLength(a, n) :
 
    # Initialise maximum length to 1
    maximum = 1;
 
    # Initialise left[] to find the
    # length of decreasing sequence
    # from left to right
    left = [0]*n;
 
    # Initialise right[] to find the
    # length of decreasing sequence
    # from right to left
    right = [0]*n;
 
    # Initially store 1 at each index of
    # left and right array
    for i in range(n) :
        left[i] = 1;
        right[i] = 1;
 
    # Iterate over the array arr[] to
    # store length of decreasing
    # sequence that can be obtained
    # at every index in the right array
    for i in range(n - 2, -1, -1) :
 
        if (a[i] > a[i + 1]) :
            right[i] = right[i + 1] + 1;
 
        # Store the length of longest
        # continuous decreasing
        # sequence in maximum
        maximum = max(maximum, right[i]);
 
    # Iterate over the array arr[] to
    # store length of decreasing
    # sequence that can be obtained
    # at every index in the left array
    for i in range(1, n) :
        if (a[i] < a[i - 1]) :
            left[i] = left[i - 1] + 1;
 
    if (n > 2) :
        # Check if we can obtain a
        # longer decreasing sequence
        # after removal of any element
        # from the array arr[] with
        # the help of left[] & right[]
        for i in range(1, n -1) :
            if (a[i - 1] > a[i + 1]) :
                maximum = max(maximum, left[i - 1] + right[i + 1]);
 
    # Return maximum length of sequence
    return maximum;
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 8, 7, 3, 5, 2, 9 ];
    n = len(arr);
 
    # Function calling
    print(maxLength(arr, n));
 
# This code is contributed by AnkitRai01

// C# program to find maximum length
// of decreasing sequence by removing
// at most one element
using System;
 
class GFG {
     
    // Function to find the maximum length
    static int maxLength(int []a, int n)
    {
        // Initialise maximum length to 1
        int maximum = 1;
     
        // Initialise left[] to find the
        // length of decreasing sequence
        // from left to right
        int []left = new int[n];
     
        // Initialise right[] to find the
        // length of decreasing sequence
        // from right to left
        int []right = new int[n];
     
        // Initially store 1 at each index of
        // left and right array
        for (int i = 0; i < n; i++) {
            left[i] = 1;
            right[i] = 1;
        }
     
        // Iterate over the array arr[] to
        // store length of decreasing
        // sequence that can be obtained
        // at every index in the right array
        for (int i = n - 2; i >= 0; i--) {
     
            if (a[i] > a[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
     
            // Store the length of longest
            // continuous decreasing
            // sequence in maximum
            maximum = Math.Max(maximum, right[i]);
        }
     
        // Iterate over the array arr[] to
        // store length of decreasing
        // sequence that can be obtained
        // at every index in the left array
        for (int i = 1; i < n; i++) {
            if (a[i] < a[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
     
        if (n > 2) {
            // Check if we can obtain a
            // longer decreasing sequence
            // after removal of any element
            // from the array arr[] with
            // the help of left[] & right[]
            for (int i = 1; i < n - 1; i++) {
                if (a[i - 1] > a[i + 1]) {
                    maximum = Math.Max(maximum, left[i - 1] + right[i + 1]);
                }
            }
        }
     
        // Return maximum length of sequence
        return maximum;
    }
     
    // Driver code
    public static void Main (String[] args)
    {
        int []arr = { 8, 7, 3, 5, 2, 9 };
        int n = arr.Length;
     
        // Function calling
        Console.WriteLine(maxLength(arr, n));
    }  
}
 
// This code is contributed by AnkitRai01

<script>
// Javascript program to find maximum length
// of decreasing sequence by removing
// at most one element
 
 
 
// Function to find the maximum length
function maxLength(a, n)
{
    // Initialise maximum length to 1
    let maximum = 1;
 
    // Initialise left[] to find the
    // length of decreasing sequence
    // from left to right
    let left = new Array(n);
 
    // Initialise right[] to find the
    // length of decreasing sequence
    // from right to left
    let right = new Array(n);
 
    // Initially store 1 at each index of
    // left and right array
    for (let i = 0; i < n; i++) {
        left[i] = 1;
        right[i] = 1;
    }
 
    // Iterate over the array arr[] to
    // store length of decreasing
    // sequence that can be obtained
    // at every index in the right array
    for (let i = n - 2; i >= 0; i--) {
 
        if (a[i] > a[i + 1]) {
            right[i] = right[i + 1] + 1;
        }
 
        // Store the length of longest
        // continuous decreasing
        // sequence in maximum
        maximum = Math.max(maximum, right[i]);
    }
 
    // Iterate over the array arr[] to
    // store length of decreasing
    // sequence that can be obtained
    // at every index in the left array
    for (let i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            left[i] = left[i - 1] + 1;
        }
    }
 
    if (n > 2) {
        // Check if we can obtain a
        // longer decreasing sequence
        // after removal of any element
        // from the array arr[] with
        // the help of left[] & right[]
        for (let i = 1; i < n - 1; i++) {
            if (a[i - 1] > a[i + 1]) {
                maximum = Math.max(maximum,
                            left[i - 1] + right[i + 1]);
            }
        }
    }
 
    // Return maximum length of sequence
    return maximum;
}
 
// Driver code
 
let arr = [ 8, 7, 3, 5, 2, 9 ];
let n = arr.length;
 
// Function calling
document.write(maxLength(arr, n) + "<br>");
 
// This code is contributed by gfgking
</script>

4

Complejidad temporal: O(n) 
Espacio auxiliar: O(n)