Length of Longest Subarray with same elements in atmost K increments | Initialize array for segment tree ; Function that builds the segment tree to return the max element in a range ; update the value in segment tree from given array ; find the middle index ; If there are more than one elements , then recur for left and right subtrees and store the max of values in this node ; Function to return the max element in the given range ; If the range is out of bounds , return - 1 ; Function that returns length of longest subarray with same elements in atmost K increments . ; Initialize the result variable Even though the K is 0 , the required longest subarray , in that case , will also be of length 1 ; Initialize the prefix sum array ; Build the prefix sum array ; Build the segment tree for range max query ; Loop through the array with a starting point as i for the required subarray till the longest subarray is found ; Performing the binary search to find the endpoint for the selected range ; Find the mid for binary search ; Find the max element in the range [ i , mid ] using Segment Tree ; Total sum of subarray after increments ; Actual sum of elements before increments ; Check if such increment is possible If true , then current i is the actual starting point of the required longest subarray ; Now for finding the endpoint for this range Perform the Binary search again with the updated start ; Store max end point for the range to give longest subarray ; If false , it means that the selected range is invalid ; Perform the Binary Search again with the updated end ; Store the length of longest subarray ; Return result ; Driver code
let segment_tree = new Array ( 4 * 1000000 ) ; function build ( A , start , end , node ) { if ( start == end ) segment_tree [ node ] = A [ start ] ; else { let mid = parseInt ( ( start + end ) / 2 , 10 ) ; segment_tree [ node ] = Math . max ( build ( A , start , mid , 2 * node + 1 ) , build ( A , mid + 1 , end , 2 * node + 2 ) ) ; } return segment_tree [ node ] ; } function query ( start , end , l , r , node ) { if ( start > r end < l ) return - 1 ; if ( start >= l && end <= r ) return segment_tree [ node ] ; let mid = parseInt ( ( start + end ) / 2 , 10 ) ; return Math . max ( query ( start , mid , l , r , 2 * node + 1 ) , query ( mid + 1 , end , l , r , 2 * node + 2 ) ) ; } function longestSubArray ( A , N , K ) { let res = 1 ; let preSum = new Array ( N + 1 ) ; preSum [ 0 ] = A [ 0 ] ; for ( let i = 0 ; i < N ; i ++ ) preSum [ i + 1 ] = preSum [ i ] + A [ i ] ; build ( A , 0 , N - 1 , 0 ) ; for ( let i = 0 ; i < N ; i ++ ) { let start = i , end = N - 1 , mid , max_index = i ; while ( start <= end ) { mid = parseInt ( ( start + end ) / 2 , 10 ) ; let max_element = query ( 0 , N - 1 , i , mid , 0 ) ; let expected_sum = ( mid - i + 1 ) * max_element ; let actual_sum = preSum [ mid + 1 ] - preSum [ i ] ; if ( expected_sum - actual_sum <= K ) { start = mid + 1 ; max_index = Math . max ( max_index , mid ) ; } else { end = mid - 1 ; } } res = Math . max ( res , max_index - i + 1 ) ; } return res ; } let arr = [ 2 , 0 , 4 , 6 , 7 ] , K = 6 ; let N = arr . length ; document . write ( longestSubArray ( arr , N , K ) ) ;