human
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"
Solution in Python:
 Give me a code to longest subarray whose elements can be made equal by maximum K increments and the other steps required?
assistant
#Here is code to longest subarray whose elements can be made equal by maximum K increments and the other steps required.
 def validSubArrLength ( arr , N , K ) :
	dp = [ 0 for i in range ( N + 1 ) ]
	pos = 0
	ans = 0
	mx = 0
	pre = 0
	q = [ ]
	for i in range ( N ) :
		while ( len ( q ) and arr [ len ( q ) - 1 ] < arr [ i ] ) :
			q . remove ( q [ len ( q ) - 1 ] )
		q . append ( i )
		if ( i == 0 ) :
			mx = arr [ i ]
			dp [ i ] = arr [ i ]
		elif ( mx <= arr [ i ] ) :
			dp [ i ] = dp [ i - 1 ] + arr [ i ]
			mx = arr [ i ]
		else :
			dp [ i ] = dp [ i - 1 ] + arr [ i ]
		if ( pre == 0 ) :
			pos = 0
		else :
			pos = pre - 1
		while ( ( i - pre + 1 ) * mx - ( dp [ i ] - dp [ pos ] ) > K and pre < i ) :
			pos = pre
			pre += 1
			while ( len ( q ) and q [ 0 ] < pre and pre < i ) :
				q . remove ( q [ 0 ] )
				mx = arr [ q [ 0 ] ]
		ans = max ( ans , i - pre + 1 )
	return ans
if __name__ == ' _ _ main _ _ ' :
	N = 6
	K = 8
	arr = [ 2 , 7 , 1 , 3 , 4 , 5 ]
	print ( validSubArrLength ( arr , N , K ) )