Maximize length of subarray of equal elements by performing at most K increment operations | Java Program for above approach ; Function to find the maximum length of subarray of equal elements after performing at most K increments ; Length of array ; 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 ; Function call
import java . util . * ; class GFG { static int maxSubarray ( int [ ] a , int k ) { int n = a . length ; int answer = 0 ; int start = 0 ; long s = 0 ; Deque < Integer > dq = new LinkedList < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { int x = a [ i ] ; while ( ! dq . isEmpty ( ) && a [ dq . peek ( ) ] <= x ) dq . poll ( ) ; dq . add ( i ) ; s += x ; long cost = ( long ) a [ dq . peekFirst ( ) ] * ( answer + 1 ) - s ; if ( cost <= ( long ) k ) answer ++ ; else { if ( dq . peekFirst ( ) == start ) dq . pollFirst ( ) ; s -= a [ start ++ ] ; } } return answer ; } public static void main ( String [ ] args ) { int [ ] a = { 2 , 2 , 4 } ; int k = 10 ; System . out . println ( maxSubarray ( a , k ) ) ; } }