Tamaño máximo del subarreglo que satisface la condición dada

Dada una array arr[] de enteros. La tarea es devolver la longitud del subarreglo de tamaño máximo de modo que cualquiera de las condiciones se cumpla: 

1. arr[k] > arr[k + 1] cuando k es impar y arr[k] < arr[k + 1] cuando k es par .
2. arr[k] > arr[k + 1] cuando k es par y arr[k] < arr[k + 1] cuando k es impar .

Ejemplos: 

Entrada: arr[] = {9, 4, 2, 10, 7, 8, 8, 1, 9} 
Salida: 5 
El subarreglo requerido es {4, 2, 10, 7, 8} que satisface la primera condición .
Entrada: arr[] = {4, 8, 12, 16} 
Salida: 2  

Enfoque: Ya que solo se requieren comparaciones entre elementos adyacentes. Entonces, si las comparaciones se van a representar mediante -1, 0, 1, entonces queremos la secuencia más larga de alternar 1, -1, 1, …, -1 (comenzando con 1 o -1) donde: 

• 0 -> arr[i] = arr[i + 1]
• 1 -> arr[i] > arr[i + 1]
• -1 -> arr[i] < arr[i + 1]

Por ejemplo, si tenemos una array arr[] = {9, 4, 2, 10, 7, 8, 8, 1, 9} entonces las comparaciones serán {1, 1, -1, 1, -1, 0 , -1, 1} y todos los subconjuntos posibles son {1} , {1, -1, 1, -1} , {0} , {-1, 1} .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Function that compares a and b
int cmp(int a, int b)
{
    return (a > b) - (a < b);
}
 
// Function to return length of longest subarray
// that satisfies one of the given conditions
int maxSubarraySize(int arr[], int n)
{
    int ans = 1;
    int anchor = 0;
 
    for (int i = 1; i < n; i++)
    {
        int c = cmp(arr[i - 1], arr[i]);
        if (c == 0)
            anchor = i;
        else if (i == n - 1 ||
                 c * cmp(arr[i], arr[i + 1]) != -1)
        {
            ans = max(ans, i - anchor + 1);
            anchor = i;
        }
    }
         
    return ans;
}
     
 
// Driver Code
int main()
{
    int arr[] = {9, 4, 2, 10, 7, 8, 8, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Print the required answer
    cout << maxSubarraySize(arr, n);
}
 
// This code is contributed by
// Surendra_Gangwar

// Java implementation of the approach
 
class GFG
{
     
// Function that compares a and b
static int cmp(int a, int b)
{
    if(a > b)
        return 1;
    else if(a == b)
        return 0;
    else
        return -1;
}
 
// Function to return length of longest subarray
// that satisfies one of the given conditions
static int maxSubarraySize(int []arr, int n)
{
    int ans = 1;
    int anchor = 0;
 
    for (int i = 1; i < n; i++)
    {
        int c = cmp(arr[i - 1], arr[i]);
        if (c == 0)
            anchor = i;
        else if (i == n - 1 ||
                c * cmp(arr[i], arr[i + 1]) != -1)
        {
            ans = Math.max(ans, i - anchor + 1);
            anchor = i;
        }
    }
         
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int []arr = {9, 4, 2, 10, 7, 8, 8, 1, 9};
    int n = arr.length;
 
    // Print the required answer
    System.out.println(maxSubarraySize(arr, n));
}
}
 
// This code has been contributed by 29AjayKumar

# Python3 implementation of the approach
 
# Function that compares a and b
def cmp(a, b):
    return (a > b) - (a < b)
 
# Function to return length of longest subarray
# that satisfies one of the given conditions
def maxSubarraySize(arr):
    N = len(arr)
    ans = 1
    anchor = 0
 
    for i in range(1, N):
        c = cmp(arr[i - 1], arr[i])
        if c == 0:
            anchor = i
        elif i == N - 1 or c * cmp(arr[i], arr[i + 1]) != -1:
            ans = max(ans, i - anchor + 1)
            anchor = i
    return ans
 
 
# Driver program
arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]
 
# Print the required answer
print(maxSubarraySize(arr))

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function that compares a and b
static int cmp(int a, int b)
{
    if(a > b)
        return 1;
    else if(a == b)
        return 0;
    else
        return -1;
}
 
// Function to return length of longest subarray
// that satisfies one of the given conditions
static int maxSubarraySize(int []arr, int n)
{
    int ans = 1;
    int anchor = 0;
 
    for (int i = 1; i < n; i++)
    {
        int c = cmp(arr[i - 1], arr[i]);
        if (c == 0)
            anchor = i;
        else if (i == n - 1 ||
                c * cmp(arr[i], arr[i + 1]) != -1)
        {
            ans = Math.Max(ans, i - anchor + 1);
            anchor = i;
        }
    }
         
    return ans;
}
     
 
// Driver Code
static void Main()
{
    int []arr = {9, 4, 2, 10, 7, 8, 8, 1, 9};
    int n = arr.Length;
 
    // Print the required answer
    Console.WriteLine(maxSubarraySize(arr, n));
}
}
 
// This code is contributed by mits

<?php
// PHP implementation of the approach
 
// Function that compares a and b
function cmp($a, $b)
{
    return ($a > $b) - ($a < $b);
}
 
// Function to return length of longest subarray
// that satisfies one of the given conditions
function maxSubarraySize($arr)
{
    $N = sizeof($arr);
    $ans = 1;
    $anchor = 0;
 
    for ($i = 1; $i < $N; $i++)
    {
        $c = cmp($arr[$i - 1], $arr[$i]);
        if ($c == 0)
            $anchor = $i;
             
        else if ($i == $N - 1 or
                 $c * cmp($arr[$i],
                          $arr[$i + 1]) != -1)
        {
            $ans = max($ans, $i - $anchor + 1);
            $anchor = $i;
        }
    }    
    return $ans;
}
 
// Driver Code
$arr = array(9, 4, 2, 10, 7, 8, 8, 1, 9);
 
// Print the required answer
echo maxSubarraySize($arr);
 
// This code is contributed by Ryuga
?>

<script>
// javascript implementation of the approach
    // Function that compares a and b
    function cmp(a , b) {
        if (a > b)
            return 1;
        else if (a == b)
            return 0;
        else
            return -1;
    }
 
    // Function to return length of longest subarray
    // that satisfies one of the given conditions
    function maxSubarraySize(arr , n) {
        var ans = 1;
        var anchor = 0;
 
        for (i = 1; i < n; i++) {
            var c = cmp(arr[i - 1], arr[i]);
            if (c == 0)
                anchor = i;
            else if (i == n - 1 || c * cmp(arr[i], arr[i + 1]) != -1) {
                ans = Math.max(ans, i - anchor + 1);
                anchor = i;
            }
        }
 
        return ans;
    }
 
    // Driver Code
     
        var arr = [ 9, 4, 2, 10, 7, 8, 8, 1, 9 ];
        var n = arr.length;
 
        // Print the required answer
        document.write(maxSubarraySize(arr, n));
 
// This code contributed by aashish1995
</script>

5

Complejidad de tiempo: O(N), donde N es la longitud de la array 
Complejidad de espacio: O(1), ya que no se ha tomado espacio adicional.