Longest subarray whose elements can be made equal by maximum K increments | Function to find maximum possible length of subarray ; Stores the sum of elements that needs to be added to the sub array ; Stores the index of the current position of subarray ; Stores the maximum length of subarray . ; Maximum element from each subarray length ; Previous index of the current subarray of maximum length ; Deque to store the indices of maximum element of each sub array ; For each array element , find the maximum length of required subarray ; Traverse the deque and update the index of maximum element . ; If it is first element then update maximum and dp [ ] ; Else check if current element exceeds max ; Update max and dp [ ] ; Update the index of the current maximum length subarray ; While current element being added to dp [ ] array exceeds K ; Update index of current position and the previous position ; Remove elements from deque and update the maximum element ; Update the maximum length of the required subarray . ; Driver code
def validSubArrLength ( arr , N , K ) : NEW_LINE INDENT dp = [ 0 for i in range ( N + 1 ) ] NEW_LINE pos = 0 NEW_LINE ans = 0 NEW_LINE mx = 0 NEW_LINE pre = 0 NEW_LINE q = [ ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT while ( len ( q ) and arr [ len ( q ) - 1 ] < arr [ i ] ) : NEW_LINE INDENT q . remove ( q [ len ( q ) - 1 ] ) NEW_LINE DEDENT q . append ( i ) NEW_LINE if ( i == 0 ) : NEW_LINE INDENT mx = arr [ i ] NEW_LINE dp [ i ] = arr [ i ] NEW_LINE DEDENT elif ( mx <= arr [ i ] ) : NEW_LINE INDENT dp [ i ] = dp [ i - 1 ] + arr [ i ] NEW_LINE mx = arr [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] = dp [ i - 1 ] + arr [ i ] NEW_LINE DEDENT if ( pre == 0 ) : NEW_LINE INDENT pos = 0 NEW_LINE DEDENT else : NEW_LINE INDENT pos = pre - 1 NEW_LINE DEDENT while ( ( i - pre + 1 ) * mx - ( dp [ i ] - dp [ pos ] ) > K and pre < i ) : NEW_LINE INDENT pos = pre NEW_LINE pre += 1 NEW_LINE while ( len ( q ) and q [ 0 ] < pre and pre < i ) : NEW_LINE INDENT q . remove ( q [ 0 ] ) NEW_LINE mx = arr [ q [ 0 ] ] NEW_LINE DEDENT DEDENT ans = max ( ans , i - pre + 1 ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 6 NEW_LINE K = 8 NEW_LINE arr = [ 2 , 7 , 1 , 3 , 4 , 5 ] NEW_LINE print ( validSubArrLength ( arr , N , K ) ) NEW_LINE DEDENT