Maximize length of subarray of equal elements by performing at most K increment operations | Python3 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 po 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
from collections import deque NEW_LINE def maxSubarray ( a , k ) : NEW_LINE INDENT n = len ( a ) NEW_LINE answer = 0 NEW_LINE start = 0 NEW_LINE s = 0 NEW_LINE dq = deque ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT x = a [ i ] NEW_LINE while ( len ( dq ) > 0 and a [ dq [ - 1 ] ] <= x ) : NEW_LINE INDENT dq . popleft ( ) NEW_LINE DEDENT dq . append ( i ) NEW_LINE s += x NEW_LINE cost = a [ dq [ 0 ] ] * ( answer + 1 ) - s NEW_LINE if ( cost <= k ) : NEW_LINE INDENT answer += 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( dq [ 0 ] == start ) : NEW_LINE INDENT dq . popleft ( ) NEW_LINE DEDENT s -= a [ start ] NEW_LINE start += 1 NEW_LINE DEDENT DEDENT return answer NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ 2 , 2 , 4 ] NEW_LINE k = 10 NEW_LINE print ( maxSubarray ( a , k ) ) NEW_LINE DEDENT