Maximize length of subarray of equal elements by performing at most K increment operations | C ++ 14 program for above approach ; Function to find the maximum length of subarray of equal elements after performing at most K increments ; Stores the size of required subarray ; Starting point of a window ; Stores the sum of window ; Iterate over array ; Current element ; Remove index of minimum elements from deque which are less than the current element ; Insert current index in deque ; Update current window sum ; Calculate required operation to make current window elements equal ; If cost is less than k ; Shift window start pointer towards right and update current window sum ; Return answer ; Driver Code ; Length of array
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define newl  " NEW_LINE " int maxSubarray ( int a [ ] , int k , int n ) { int answer = 0 ; int start = 0 ; long int s = 0 ; deque < int > dq ; for ( int i = 0 ; i < n ; i ++ ) { int x = a [ i ] ; while ( ! dq . empty ( ) && a [ dq . front ( ) ] <= x ) dq . pop_front ( ) ; dq . push_back ( i ) ; s += x ; long int cost = ( long int ) a [ dq . front ( ) ] * ( answer + 1 ) - s ; if ( cost <= ( long int ) k ) answer ++ ; else { if ( dq . front ( ) == start ) dq . pop_front ( ) ; s -= a [ start ++ ] ; } } return answer ; } int main ( ) { int a [ ] = { 2 , 2 , 4 } ; int k = 10 ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << ( maxSubarray ( a , k , n ) ) ; return 0 ; }