Longitud del subarreglo más largo con media aritmética máxima.

Dada una array de n elementos, encuentre la sub-array más larga con la mayor media aritmética. La longitud del subarreglo debe ser mayor que 1 y la media debe calcularse solo como un número entero.
Ejemplos: 
 

Input : arr[] = {3, 2, 1, 2}
Output : 2
sub-array 3, 2 has greatest arithmetic mean

Input :arr[] = {3, 3, 3, 2}
Output : 3

La idea es encontrar primero la mayor media de dos elementos consecutivos de la array. Vuelva a iterar sobre la array e intente encontrar la secuencia más larga en la que cada elemento debe ser mayor o igual que la mayor media calculada.
El enfoque anterior funciona debido a estos puntos clave: 
 

• La longitud de secuencia mínima posible es 2 y, por lo tanto, la mayor media de dos elementos consecutivos siempre será parte del resultado.
• Cualquier elemento que sea igual o mayor que la media calculada puede ser parte de la secuencia más larga.

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum distance
// between unequal elements
int longestSubarray(int arr[], int n)
{
 
    // Calculate maxMean
    int maxMean = 0;
    for (int i = 1; i < n; i++)
        maxMean = max(maxMean,
                      (arr[i] + arr[i - 1]) / 2);
 
    // Iterate over array and calculate largest subarray
    // with all elements greater or equal to maxMean
    int ans = 0;
    int subarrayLength = 0;
    for (int i = 0; i < n; i++)
        if (arr[i] >= maxMean)
            ans = max(ans, ++subarrayLength);
        else
            subarrayLength = 0;
 
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 4, 3, 3, 2, 1, 4 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << longestSubarray(arr, n);
 
    return 0;
}

// Java implementation of the above approach
import java.io.*;
 
class GFG
{
     
// Function to find maximum distance
// between unequal elements
static int longestSubarray(int arr[], int n)
{
 
    // Calculate maxMean
    int maxMean = 0;
    for (int i = 1; i < n; i++)
        maxMean = Math.max(maxMean,
                    (arr[i] + arr[i - 1]) / 2);
 
    // Iterate over array and calculate largest subarray
    // with all elements greater or equal to maxMean
    int ans = 0;
    int subarrayLength = 0;
    for (int i = 0; i < n; i++)
        if (arr[i] >= maxMean)
            ans = Math.max(ans, ++subarrayLength);
        else
            subarrayLength = 0;
 
    return ans;
}
 
// Driver code
public static void main (String[] args)
{
 
    int arr[] = { 4, 3, 3, 2, 1, 4 };
    int n = arr.length;
    System.out.println (longestSubarray(arr, n));
}
}
 
// This code is contributed by ajit_00023

     
# Python implementation of the above approach
 
# Function to find maximum distance
# between unequal elements
def longestSubarray(arr, n):
 
    # Calculate maxMean
    maxMean = 0;
    for i in range(1, n):
        maxMean = max(maxMean,
                    (arr[i] + arr[i - 1]) // 2);
 
    # Iterate over array and calculate largest subarray
    # with all elements greater or equal to maxMean
    ans = 0;
    subarrayLength = 0;
    for i in range(n):
        if (arr[i] >= maxMean):
            subarrayLength += 1;
            ans = max(ans, subarrayLength);
        else:
            subarrayLength = 0;
 
    return ans;
 
# Driver code
arr = [ 4, 3, 3, 2, 1, 4 ];
 
n = len(arr);
 
print(longestSubarray(arr, n));
 
# This code contributed by PrinciRaj1992

// C# program for the above approach
using System;
 
class GFG
{
     
    // Function to find maximum distance
    // between unequal elements
    static int longestSubarray(int []arr,
                               int n)
    {
     
        // Calculate maxMean
        int maxMean = 0;
        for (int i = 1; i < n; i++)
            maxMean = Math.Max(maxMean,
                              (arr[i] + arr[i - 1]) / 2);
     
        // Iterate over array and calculate
        // largest subarray with all elements
        // greater or equal to maxMean
        int ans = 0;
        int subarrayLength = 0;
        for (int i = 0; i < n; i++)
            if (arr[i] >= maxMean)
                ans = Math.Max(ans, ++subarrayLength);
            else
                subarrayLength = 0;
     
        return ans;
    }
     
    // Driver code
    public static void Main ()
    {
     
        int []arr = { 4, 3, 3, 2, 1, 4 };
        int n = arr.Length;
        Console.WriteLine(longestSubarray(arr, n));
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript implementation of the above approach
 
// Function to find maximum distance
// between unequal elements
function longestSubarray(arr, n)
{
 
    // Calculate maxMean
    var maxMean = 0;
    for (var i = 1; i < n; i++)
        maxMean = Math.max(maxMean,
                      parseInt((arr[i] + arr[i - 1]) / 2));
 
    // Iterate over array and calculate largest subarray
    // with all elements greater or equal to maxMean
    var ans = 0;
    var subarrayLength = 0;
    for (var i = 0; i < n; i++)
        if (arr[i] >= maxMean)
            ans = Math.max(ans, ++subarrayLength);
        else
            subarrayLength = 0;
 
    return ans;
}
 
// Driver code
var arr = [ 4, 3, 3, 2, 1, 4 ];
var n = arr.length;
document.write( longestSubarray(arr, n));
 
</script>

3

Complejidad de tiempo : O(N)

Espacio Auxiliar: O(1)