Longest Sub-array with maximum average value
Given an array arr[] of n integers. The task is to find the maximum length of the sub-array which has the maximum average value (average of the elements of the sub-array).
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
Examples:
Input: arr[] = {2, 3, 4, 5, 6}
Output: 1
{6} is the required sub-array
Input: arr[] = {6, 1, 6, 6, 0}
Output: 2
{6} and {6, 6} are the sub-arrays with maximum average value.
Approach:
- Average of any sub-array cannot exceed the maximum value of the array.
- The possible maximum value of the average will be the maximum element from the array.
- So to find the maximum length sub-array with the maximum average value, we have to find the max length of the sub-array where every element of the sub-array is same and equal to the maximum element from the array.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the max length of the // sub-array that have the maximum average // (average value of the elements) int maxLenSubArr( int a[], int n) { int count, j; int cm = 1, max = 0; // Finding the maximum value for ( int i = 0; i < n; i++) { if (a[i] > max) max = a[i]; } for ( int i = 0; i < n - 1;) { count = 1; // If consecutive maximum found if (a[i] == a[i + 1] && a[i] == max) { // Find the max length of consecutive max for (j = i + 1; j < n; j++) { if (a[j] == max) { count++; i++; } else break ; } if (count > cm) cm = count; } else i++; } return cm; } // Driver code int main() { int arr[] = { 6, 1, 6, 6, 0 }; int n = sizeof (arr) / sizeof (arr[0]); cout << maxLenSubArr(arr, n); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the max length of the // sub-array that have the maximum average // (average value of the elements) static int maxLenSubArr( int a[], int n) { int count, j; int cm = 1 , max = 0 ; // Finding the maximum value for ( int i = 0 ; i < n; i++) { if (a[i] > max) max = a[i]; } for ( int i = 0 ; i < n - 1 ; ) { count = 1 ; // If consecutive maximum found if (a[i] == a[i + 1 ] && a[i] == max) { // Find the max length of consecutive max for (j = i + 1 ; j < n; j++) { if (a[j] == max) { count++; i++; } else break ; } if (count > cm) cm = count; } else i++; } return cm; } // Driver code public static void main(String[] args) { int arr[] = { 6 , 1 , 6 , 6 , 0 }; int n = arr.length; System.out.println(maxLenSubArr(arr, n)); } } // This code is contributed by Code_Mech. |
Python3
# Python3 implementation of the approach # Function to return the max length of the # sub-array that have the maximum average # (average value of the elements) def maxLenSubArr(a, n): cm, Max = 1 , 0 # Finding the maximum value for i in range ( 0 , n): if a[i] > Max : Max = a[i] i = 0 while i < n - 1 : count = 1 # If consecutive maximum found if a[i] = = a[i + 1 ] and a[i] = = Max : # Find the max length of # consecutive max for j in range (i + 1 , n): if a[j] = = Max : count + = 1 i + = 1 else : break if count > cm: cm = count else : i + = 1 i + = 1 return cm # Driver code if __name__ = = "__main__" : arr = [ 6 , 1 , 6 , 6 , 0 ] n = len (arr) print (maxLenSubArr(arr, n)) # This code is contributed by # Rituraj Jain |
C#
// C# implementation of the approach using System; class GFG { // Function to return the max length of the // sub-array that have the maximum average // (average value of the elements) static int maxLenSubArr( int []a, int n) { int count, j; int cm = 1, max = 0; // Finding the maximum value for ( int i = 0; i < n; i++) { if (a[i] > max) max = a[i]; } for ( int i = 0; i < n - 1; ) { count = 1; // If consecutive maximum found if (a[i] == a[i + 1] && a[i] == max) { // Find the max length of consecutive max for (j = i + 1; j < n; j++) { if (a[j] == max) { count++; i++; } else break ; } if (count > cm) cm = count; } else i++; } return cm; } // Driver code static public void Main () { int []arr = { 6, 1, 6, 6, 0 }; int n = arr.Length; Console.WriteLine(maxLenSubArr(arr, n)); } } // This code is contributed by ajit. |
PHP
<?php // PHP implementation of the approach // Function to return the max length of the // sub-array that have the maximum average // (average value of the elements) function maxLenSubArr( $a , $n ) { $cm = 1 ; $max = 0; // Finding the maximum value for ( $i = 0; $i < $n ; $i ++) { if ( $a [ $i ] > $max ) $max = $a [ $i ]; } for ( $i = 0; $i < $n - 1;) { $count = 1; // If consecutive maximum found if ( $a [ $i ] == $a [ $i + 1] && $a [ $i ] == $max ) { // Find the max length of // consecutive max for ( $j = $i + 1; $j < $n ; $j ++) { if ( $a [ $j ] == $max ) { $count ++; $i ++; } else break ; } if ( $count > $cm ) $cm = $count ; } else $i ++; } return $cm ; } // Driver code $arr = array ( 6, 1, 6, 6, 0 ); $n = sizeof( $arr ); echo maxLenSubArr( $arr , $n ); // This code is contributed by Ryuga ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the max length of the // sub-array that have the maximum average // (average value of the elements) function maxLenSubArr(a, n) { let count, j; let cm = 1, max = 0; // Finding the maximum value for (let i = 0; i < n; i++) { if (a[i] > max) max = a[i]; } for (let i = 0; i < n - 1; ) { count = 1; // If consecutive maximum found if (a[i] == a[i + 1] && a[i] == max) { // Find the max length of consecutive max for (j = i + 1; j < n; j++) { if (a[j] == max) { count++; i++; } else break ; } if (count > cm) cm = count; } else i++; } return cm; } let arr = [ 6, 1, 6, 6, 0 ]; let n = arr.length; document.write(maxLenSubArr(arr, n)); </script> |
Output:
2
Time Complexity: O(n2)
Auxiliary Space: O(1)