Longitud máxima de subarreglo estrictamente creciente después de eliminar como máximo un elemento

Dada una array arr[] , la tarea es eliminar como máximo un elemento y calcular la longitud máxima del subarreglo estrictamente creciente.

Ejemplos: 

Entrada: arr[] = {1, 2, 5, 3, 4} 
Salida: 4 
Después de eliminar 5, el arreglo resultante será {1, 2, 3, 4} 
y la longitud máxima de su subarreglo estrictamente creciente es 4.

Entrada: arr[] = {1, 2} 
Salida: 2 
La array completa ya es estrictamente creciente. 

Acercarse:  

• Cree dos arrays pre[] y pos[] de tamaño N.
• Iterar sobre la array de entrada arr[] desde (0, N) para averiguar la contribución del elemento actual arr[i] en la array hasta ahora [0, i) y actualizar la array pre[] si contribuye estrictamente subarreglo creciente.
• Itere sobre la array de entrada arr[] desde [N – 2, 0] para averiguar la contribución del elemento actual arr[j] en la array hasta ahora (N, j) y actualice la array pos[] si arr[j ] contribuye en el subarreglo creciente más largo.
• Calcule la longitud máxima del subarreglo estrictamente creciente sin eliminar ningún elemento.
• Iterar sobre la array pre[] y pos[] para averiguar la contribución del elemento actual al excluir ese elemento.
• Mantener una variable ans para encontrar el máximo encontrado hasta ahora.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum length of
// strictly increasing subarray after
// removing atmost one element
int maxIncSubarr(int a[], int n)
{
    // Create two arrays pre and pos
    int pre[n] = { 0 };
    int pos[n] = { 0 };
    pre[0] = 1;
    pos[n - 1] = 1;
    int l = 0;
 
    // Find out the contribution of the current
    // element in array[0, i] and update pre[i]
    for (int i = 1; i < n; i++) {
        if (a[i] > a[i - 1])
            pre[i] = pre[i - 1] + 1;
        else
            pre[i] = 1;
    }
 
    // Find out the contribution of the current
    // element in array[N - 1, i] and update pos[i]
    l = 1;
    for (int i = n - 2; i >= 0; i--) {
        if (a[i] < a[i + 1])
            pos[i] = pos[i + 1] + 1;
        else
            pos[i] = 1;
    }
 
    // Calculate the maximum length of the
    // strictly increasing subarray without
    // removing any element
    int ans = 0;
    l = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] > a[i - 1])
            l++;
        else
            l = 1;
        ans = max(ans, l);
    }
 
    // Calculate the maximum length of the
    // strictly increasing subarray after
    // removing the current element
    for (int i = 1; i <= n - 2; i++) {
        if (a[i - 1] < a[i + 1])
            ans = max(pre[i - 1] + pos[i + 1], ans);
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2 };
    int n = sizeof(arr) / sizeof(int);
 
    cout << maxIncSubarr(arr, n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
    // Function to return the maximum length of
    // strictly increasing subarray after
    // removing atmost one element
    static int maxIncSubarr(int a[], int n)
    {
        // Create two arrays pre and pos
        int pre[] = new int[n] ;
        int pos[] = new int[n] ;
        pre[0] = 1;
        pos[n - 1] = 1;
        int l = 0;
     
        // Find out the contribution of the current
        // element in array[0, i] and update pre[i]
        for (int i = 1; i < n; i++)
        {
            if (a[i] > a[i - 1])
                pre[i] = pre[i - 1] + 1;
            else
                pre[i] = 1;
        }
     
        // Find out the contribution of the current
        // element in array[N - 1, i] and update pos[i]
        l = 1;
        for (int i = n - 2; i >= 0; i--)
        {
            if (a[i] < a[i + 1])
                pos[i] = pos[i + 1] + 1;
            else
                pos[i] = 1;
        }
     
        // Calculate the maximum length of the
        // strictly increasing subarray without
        // removing any element
        int ans = 0;
        l = 1;
        for (int i = 1; i < n; i++)
        {
            if (a[i] > a[i - 1])
                l++;
            else
                l = 1;
            ans = Math.max(ans, l);
        }
     
        // Calculate the maximum length of the
        // strictly increasing subarray after
        // removing the current element
        for (int i = 1; i <= n - 2; i++)
        {
            if (a[i - 1] < a[i + 1])
                ans = Math.max(pre[i - 1] +
                                pos[i + 1], ans);
        }
        return ans;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int arr[] = {1, 2};
        int n = arr.length;
     
        System.out.println(maxIncSubarr(arr, n));
    }
}
 
// This code is contributed by AnkitRai01

# Python implementation of the approach
 
# Function to return the maximum length of
# strictly increasing subarray after
# removing atmost one element
def maxIncSubarr(a, n):
     
    # Create two arrays pre and pos
    pre = [0] * n;
    pos = [0] * n;
    pre[0] = 1;
    pos[n - 1] = 1;
    l = 0;
 
    # Find out the contribution of the current
    # element in array[0, i] and update pre[i]
    for i in range(1, n):
        if (a[i] > a[i - 1]):
            pre[i] = pre[i - 1] + 1;
        else:
            pre[i] = 1;
     
    # Find out the contribution of the current
    # element in array[N - 1, i] and update pos[i]
    l = 1;
    for i in range(n - 2, -1, -1):
        if (a[i] < a[i + 1]):
            pos[i] = pos[i + 1] + 1;
        else:
            pos[i] = 1;
     
    # Calculate the maximum length of the
    # strictly increasing subarray without
    # removing any element
    ans = 0;
    l = 1;
    for i in range(1, n):
        if (a[i] > a[i - 1]):
            l += 1;
        else:
            l = 1;
        ans = max(ans, l);
     
    # Calculate the maximum length of the
    # strictly increasing subarray after
    # removing the current element
    for i in range(1, n - 1):
        if (a[i - 1] < a[i + 1]):
            ans = max(pre[i - 1] + pos[i + 1], ans);
     
    return ans;
 
# Driver code
if __name__ == '__main__':
    arr = [ 1, 2 ];
    n = len(arr);
 
    print(maxIncSubarr(arr, n));
     
# This code is contributed by PrinciRaj1992

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the maximum length of
    // strictly increasing subarray after
    // removing atmost one element
    static int maxIncSubarr(int []a, int n)
    {
        // Create two arrays pre and pos
        int []pre = new int[n] ;
        int []pos = new int[n] ;
        pre[0] = 1;
        pos[n - 1] = 1;
        int l = 0;
     
        // Find out the contribution of the current
        // element in array[0, i] and update pre[i]
        for (int i = 1; i < n; i++)
        {
            if (a[i] > a[i - 1])
                pre[i] = pre[i - 1] + 1;
            else
                pre[i] = 1;
        }
     
        // Find out the contribution of the current
        // element in array[N - 1, i] and update pos[i]
        l = 1;
        for (int i = n - 2; i >= 0; i--)
        {
            if (a[i] < a[i + 1])
                pos[i] = pos[i + 1] + 1;
            else
                pos[i] = 1;
        }
     
        // Calculate the maximum length of the
        // strictly increasing subarray without
        // removing any element
        int ans = 0;
        l = 1;
        for (int i = 1; i < n; i++)
        {
            if (a[i] > a[i - 1])
                l++;
            else
                l = 1;
            ans = Math.Max(ans, l);
        }
     
        // Calculate the maximum length of the
        // strictly increasing subarray after
        // removing the current element
        for (int i = 1; i <= n - 2; i++)
        {
            if (a[i - 1] < a[i + 1])
                ans = Math.Max(pre[i - 1] +
                                pos[i + 1], ans);
        }
        return ans;
    }
     
    // Driver code
    public static void Main()
    {
        int []arr = {1, 2};
        int n = arr.Length;
     
        Console.WriteLine(maxIncSubarr(arr, n));
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript implementation of the approach
 
// Function to return the maximum length of
// strictly increasing subarray after
// removing atmost one element
function maxIncSubarr(a, n)
{
     
    // Create two arrays pre and pos
    let pre = new Array(n);
    let pos = new Array(n);
    pre.fill(0);
    pos.fill(0);
    pre[0] = 1;
    pos[n - 1] = 1;
    let l = 0;
 
    // Find out the contribution of the current
    // element in array[0, i] and update pre[i]
    for(let i = 1; i < n; i++)
    {
        if (a[i] > a[i - 1])
            pre[i] = pre[i - 1] + 1;
        else
            pre[i] = 1;
    }
 
    // Find out the contribution of the current
    // element in array[N - 1, i] and update pos[i]
    l = 1;
    for(let i = n - 2; i >= 0; i--)
    {
        if (a[i] < a[i + 1])
            pos[i] = pos[i + 1] + 1;
        else
            pos[i] = 1;
    }
 
    // Calculate the maximum length of the
    // strictly increasing subarray without
    // removing any element
    let ans = 0;
    l = 1;
    for(let i = 1; i < n; i++)
    {
        if (a[i] > a[i - 1])
            l++;
        else
            l = 1;
        ans = Math.max(ans, l);
    }
 
    // Calculate the maximum length of the
    // strictly increasing subarray after
    // removing the current element
    for(let i = 1; i <= n - 2; i++)
    {
        if (a[i - 1] < a[i + 1])
            ans = Math.max(pre[i - 1] +
                           pos[i + 1], ans);
    }
    return ans;
}
 
// Driver code
let arr = [ 1, 2 ];
let n = arr.length;
 
document.write(maxIncSubarr(arr, n));
 
// This code is contributed by rameshtravel07
 
</script>

2

Complejidad de tiempo: O(N)

Complejidad espacial: O(N)