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 Program
function validSubArrLength ( arr , N , K ) { var dp = Array ( N + 1 ) ; var pos = 0 ; var ans = 0 ; var mx = 0 ; var pre = 0 ; var q = [ ] ; for ( var i = 0 ; i < N ; i ++ ) { while ( q . length != 0 && arr [ q [ q . length - 1 ] ] < arr [ i ] ) q . pop ( ) ; q . push ( i ) ; if ( i == 0 ) { mx = arr [ i ] ; dp [ i ] = arr [ i ] ; } else if ( 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 && pre < i ) { pos = pre ; pre ++ ; while ( q . length != 0 && q [ 0 ] < pre && pre < i ) { q . shift ( ) ; mx = arr [ q [ 0 ] ] ; } } ans = Math . max ( ans , i - pre + 1 ) ; } return ans ; } var N = 6 ; var K = 8 ; var arr = [ 2 , 7 , 1 , 3 , 4 , 5 ] ; document . write ( validSubArrLength ( arr , N , K ) ) ;