Sub-arreglo de longitud máxima que satisface las condiciones dadas – Part 1

Dado un arreglo arr[] de N enteros, la tarea es encontrar la longitud máxima de cualquier subarreglo de arr[] que satisfaga una de las condiciones dadas: 

1. El subarreglo es estrictamente creciente.
2. El subarreglo es estrictamente decreciente.
3. El subarreglo primero es estrictamente creciente y luego estrictamente decreciente.

Ejemplos:  

Entrada: arr[] = {1, 2, 2, 1, 3} 
Salida: 2 
{1, 2}, {2, 1} y {1, 3} son los subarreglos válidos.

Entrada: arr[] = {5, 4, 3, 2, 1, 2, 3, 4} 
Salida: 5 
{5, 4, 3, 2, 1} es el subarreglo requerido. 
 

Enfoque: Cree una array incEnding[] donde incEnding[i] almacenará la longitud del subarreglo creciente más grande de la array dada que termina en el índice i . De manera similar, cree otra array decStarting[] donde decStarting[i] almacenará la longitud del subarreglo decreciente más grande de la array dada comenzando en el índice i . Ahora comience a recorrer la array original y para cada elemento, asuma que es la mitad de la subarreferencia requerida y luego la longitud de la subarreferencia requerida más grande cuya mitad en el índice i será incEnding[i] + decStarting[i] – 1 . Tenga en cuenta que 1se resta porque arr[i] se contará dos veces tanto para el subarreglo creciente como para el decreciente.

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 largest
// required sub-array
int largestSubArr(int arr[], int n)
{
 
    // incEnding[i] will store the length
    // of the largest increasing subarray
    // ending at arr[i]
    int incEnding[n] = { 0 };
    incEnding[0] = 1;
    for (int i = 1; i < n; i++) {
 
        // If current element is greater than
        // the previous element then it
        // can be a part of the previous
        // increasing subarray
        if (arr[i - 1] < arr[i])
            incEnding[i] = incEnding[i - 1] + 1;
        else
            incEnding[i] = 1;
    }
 
    // decStarting[i] will store the length
    // of the largest decreasing subarray
    // starting at arr[i]
    int decStarting[n] = { 0 };
    decStarting[n - 1] = 1;
    for (int i = n - 2; i >= 0; i--) {
 
        // If current element is greater than
        // the next element then it can be a part
        // of the decreasing subarray
        // with the next element
        if (arr[i + 1] < arr[i])
            decStarting[i] = decStarting[i + 1] + 1;
        else
            decStarting[i] = 1;
    }
 
    // To store the length of the
    // maximum required subarray
    int maxSubArr = 0;
 
    // Assume every element to be the mid
    // point of the required array
    for (int i = 0; i < n; i++) {
 
        // 1 has to be subtracted because the
        // current element will be counted for
        // both the increasing and
        // the decreasing subarray
        maxSubArr = max(maxSubArr, incEnding[i]
                                       + decStarting[i] - 1);
    }
 
    return maxSubArr;
}
 
// Driver code
int main()
{
 
    int arr[] = { 1, 2, 2, 1, 3 };
    int n = sizeof(arr) / sizeof(int);
 
    cout << largestSubArr(arr, n);
 
    return 0;
}

// Java implementation of the above approach
class GFG
{
     
    // Function to return the largest
    // required sub-array
    static int largestSubArr(int arr[], int n)
    {
     
        // incEnding[i] will store the length
        // of the largest increasing subarray
        // ending at arr[i]
        int incEnding[] = new int[n];
         
        int i;
        for(i = 0; i < n ; i++)
            incEnding[i] = 0;
             
        incEnding[0] = 1;
         
        for (i = 1; i < n; i++)
        {
     
            // If current element is greater than
            // the previous element then it
            // can be a part of the previous
            // increasing subarray
            if (arr[i - 1] < arr[i])
                incEnding[i] = incEnding[i - 1] + 1;
            else
                incEnding[i] = 1;
        }
     
        // decStarting[i] will store the length
        // of the largest decreasing subarray
        // starting at arr[i]
        int decStarting[] = new int[n];
         
        for(i = 0; i < n ; i++)
            decStarting[i] = 0;
             
        decStarting[n - 1] = 1;
         
        for (i = n - 2; i >= 0; i--)
        {
     
            // If current element is greater than
            // the next element then it can be a part
            // of the decreasing subarray
            // with the next element
            if (arr[i + 1] < arr[i])
                decStarting[i] = decStarting[i + 1] + 1;
            else
                decStarting[i] = 1;
        }
     
        // To store the length of the
        // maximum required subarray
        int maxSubArr = 0;
     
        // Assume every element to be the mid
        // point of the required array
        for (i = 0; i < n; i++)
        {
     
            // 1 has to be subtracted because the
            // current element will be counted for
            // both the increasing and
            // the decreasing subarray
            maxSubArr = Math.max(maxSubArr, incEnding[i] +
                                            decStarting[i] - 1);
        }
        return maxSubArr;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int arr[] = { 1, 2, 2, 1, 3 };
        int n = arr.length;
         
        System.out.println(largestSubArr(arr, n));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to return the largest
# required sub-array
def largestSubArr(arr, n) :
 
    # incEnding[i] will store the length
    # of the largest increasing subarray
    # ending at arr[i]
    incEnding = [0] * n
    incEnding[0] = 1
    for i in range(1, n) :
 
        # If current element is greater than
        # the previous element then it
        # can be a part of the previous
        # increasing subarray
        if (arr[i - 1] < arr[i]) :
            incEnding[i] = incEnding[i - 1] + 1
        else :
            incEnding[i] = 1
 
    # decStarting[i] will store the length
    # of the largest decreasing subarray
    # starting at arr[i]
    decStarting = [0] * n
    decStarting[n - 1] = 1
    for i in range(n - 2, -1, -1):
 
        # If current element is greater than
        # the next element then it can be a part
        # of the decreasing subarray
        # with the next element
        if (arr[i + 1] < arr[i]) :
            decStarting[i] = decStarting[i + 1] + 1
        else :
            decStarting[i] = 1
 
    # To store the length of the
    # maximum required subarray
    maxSubArr = 0
 
    # Assume every element to be the mid
    # point of the required array
    for i in range(n):
 
        # 1 has to be subtracted because the
        # current element will be counted for
        # both the increasing and
        # the decreasing subarray
        maxSubArr = max(maxSubArr, incEnding[i] +
                                 decStarting[i] - 1)
 
    return maxSubArr
     
# Driver code
arr = [ 1, 2, 2, 1, 3 ]
n = len(arr)
 
print(largestSubArr(arr, n))
 
# This code is contributed by
# divyamohan123

// C# implementation of the above approach
using System;        
 
class GFG
{
     
    // Function to return the largest
    // required sub-array
    static int largestSubArr(int []arr, int n)
    {
     
        // incEnding[i] will store the length
        // of the largest increasing subarray
        // ending at arr[i]
        int []incEnding = new int[n];
         
        int i;
        for(i = 0; i < n ; i++)
            incEnding[i] = 0;
             
        incEnding[0] = 1;
         
        for (i = 1; i < n; i++)
        {
     
            // If current element is greater than
            // the previous element then it
            // can be a part of the previous
            // increasing subarray
            if (arr[i - 1] < arr[i])
                incEnding[i] = incEnding[i - 1] + 1;
            else
                incEnding[i] = 1;
        }
     
        // decStarting[i] will store the length
        // of the largest decreasing subarray
        // starting at arr[i]
        int []decStarting = new int[n];
         
        for(i = 0; i < n ; i++)
            decStarting[i] = 0;
             
        decStarting[n - 1] = 1;
         
        for (i = n - 2; i >= 0; i--)
        {
     
            // If current element is greater than
            // the next element then it can be a part
            // of the decreasing subarray
            // with the next element
            if (arr[i + 1] < arr[i])
                decStarting[i] = decStarting[i + 1] + 1;
            else
                decStarting[i] = 1;
        }
     
        // To store the length of the
        // maximum required subarray
        int maxSubArr = 0;
     
        // Assume every element to be the mid
        // point of the required array
        for (i = 0; i < n; i++)
        {
     
            // 1 has to be subtracted because the
            // current element will be counted for
            // both the increasing and
            // the decreasing subarray
            maxSubArr = Math.Max(maxSubArr, incEnding[i] +
                                            decStarting[i] - 1);
        }
        return maxSubArr;
    }
     
    // Driver code
    public static void Main (String[] args)
    {
        int []arr = { 1, 2, 2, 1, 3 };
        int n = arr.Length;
         
        Console.WriteLine(largestSubArr(arr, n));
    }
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript implementation of the approach
 
// Function to return the largest
// required sub-array
function largestSubArr(arr, n)
{
     
    // incEnding[i] will store the length
    // of the largest increasing subarray
    // ending at arr[i]
    var incEnding = Array(n).fill(0);
    incEnding[0] = 1;
     
    for(var i = 1; i < n; i++)
    {
         
        // If current element is greater than
        // the previous element then it
        // can be a part of the previous
        // increasing subarray
        if (arr[i - 1] < arr[i])
            incEnding[i] = incEnding[i - 1] + 1;
        else
            incEnding[i] = 1;
    }
 
    // decStarting[i] will store the length
    // of the largest decreasing subarray
    // starting at arr[i]
    var decStarting = Array(n).fill(0);
    decStarting[n - 1] = 1;
     
    for(var i = n - 2; i >= 0; i--)
    {
         
        // If current element is greater than
        // the next element then it can be a part
        // of the decreasing subarray
        // with the next element
        if (arr[i + 1] < arr[i])
            decStarting[i] = decStarting[i + 1] + 1;
        else
            decStarting[i] = 1;
    }
 
    // To store the length of the
    // maximum required subarray
    var maxSubArr = 0;
 
    // Assume every element to be the mid
    // point of the required array
    for(var i = 0; i < n; i++)
    {
         
        // 1 has to be subtracted because the
        // current element will be counted for
        // both the increasing and
        // the decreasing subarray
        maxSubArr = Math.max(maxSubArr,
                             incEnding[i] +
                             decStarting[i] - 1);
    }
    return maxSubArr;
}
 
// Driver code
var arr = [ 1, 2, 2, 1, 3 ];
var n = arr.length;
 
document.write(largestSubArr(arr, n));
 
// This code is contributed by itsok
 
</script>

2