Longest subarray having average greater than or equal to x | CPP program to find Longest subarray having average greater than or equal to x . ; Comparison function used to sort preSum vector . ; Function to find index in preSum vector upto which all prefix sum values are less than or equal to val . ; Starting and ending index of search space . ; To store required index value . ; If middle value is less than or equal to val then index can lie in mid + 1. . n else it lies in 0. . mid - 1. ; Function to find Longest subarray having average greater than or equal to x . ; Update array by subtracting x from each element . ; Length of Longest subarray . ; Vector to store pair of prefix sum and corresponding ending index value . ; To store current value of prefix sum . ; To store minimum index value in range 0. . i of preSum vector . ; Insert values in preSum vector . ; Update minInd array . ; If sum is greater than or equal to 0 , then answer is i + 1. ; If sum is less than 0 , then find if there is a prefix array having sum that needs to be added to current sum to make its value greater than or equal to 0. If yes , then compare length of updated subarray with maximum length found so far . ; Driver code .
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool compare ( const pair < int , int > & a , const pair < int , int > & b ) { if ( a . first == b . first ) return a . second < b . second ; return a . first < b . first ; } int findInd ( vector < pair < int , int > > & preSum , int n , int val ) { int l = 0 ; int h = n - 1 ; int mid ; int ans = -1 ; while ( l <= h ) { mid = ( l + h ) / 2 ; if ( preSum [ mid ] . first <= val ) { ans = mid ; l = mid + 1 ; } else h = mid - 1 ; } return ans ; } int LongestSub ( int arr [ ] , int n , int x ) { int i ; for ( i = 0 ; i < n ; i ++ ) arr [ i ] -= x ; int maxlen = 0 ; vector < pair < int , int > > preSum ; int sum = 0 ; int minInd [ n ] ; for ( i = 0 ; i < n ; i ++ ) { sum = sum + arr [ i ] ; preSum . push_back ( { sum , i } ) ; } sort ( preSum . begin ( ) , preSum . end ( ) , compare ) ; minInd [ 0 ] = preSum [ 0 ] . second ; for ( i = 1 ; i < n ; i ++ ) { minInd [ i ] = min ( minInd [ i - 1 ] , preSum [ i ] . second ) ; } sum = 0 ; for ( i = 0 ; i < n ; i ++ ) { sum = sum + arr [ i ] ; if ( sum >= 0 ) maxlen = i + 1 ; else { int ind = findInd ( preSum , n , sum ) ; if ( ind != -1 && minInd [ ind ] < i ) maxlen = max ( maxlen , i - minInd [ ind ] ) ; } } return maxlen ; } int main ( ) { int arr [ ] = { -2 , 1 , 6 , -3 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int x = 3 ; cout << LongestSub ( arr , n , x ) ; return 0 ; }