Maximize length of longest subarray consisting of same elements by at most K decrements | C ++ program to implement the above approach ; Function to construct Segment Tree to return the minimum element in a range ; If leaf nodes of the tree are found ; Update the value in segment tree from given array ; Divide left and right subtree ; Stores smallest element in subarray { arr [ start ] , arr [ mid ] } ; Stores smallest element in subarray { arr [ mid + 1 ] , arr [ end ] } ; Stores smallest element in subarray { arr [ start ] , arr [ end ] } ; Function to find the smallest element present in a subarray ; If elements of the subarray are not in the range [ l , r ] ; If all the elements of the subarray are in the range [ l , r ] ; Divide tree into left and right subtree ; Stores smallest element in left subtree ; Stores smallest element in right subtree ; Function that find length of longest subarray with all equal elements in atmost K decrements ; Stores length of longest subarray with all equal elements in atmost K decrements . ; Store the prefix sum array ; Calculate the prefix sum array ; Build the segment tree for range min query ; Traverse the array ; Stores start index of the subarray ; Stores end index of the subarray ; Stores end index of the longest subarray ; Performing the binary search to find the endpoint for the selected range ; Find the mid for binary search ; Find the smallest element in range [ i , mid ] using Segment Tree ; Stores total sum of subarray after K decrements ; Stores sum of elements of subarray before K decrements ; If subarray found with all equal elements ; Update start ; Update max_index ; If false , it means that the selected range is invalid ; Update end ; Store the length of longest subarray ; Return result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int build ( int tree [ ] , int * A , int start , int end , int node ) { if ( start == end ) { tree [ node ] = A [ start ] ; return tree [ node ] ; } int mid = ( start + end ) / 2 ; int X = build ( tree , A , start , mid , 2 * node + 1 ) ; int Y = build ( tree , A , mid + 1 , end , 2 * node + 2 ) ; return tree [ node ] = min ( X , Y ) ; } int query ( int tree [ ] , int start , int end , int l , int r , int node ) { if ( start > r end < l ) return INT_MAX ; if ( start >= l && end <= r ) return tree [ node ] ; int mid = ( start + end ) / 2 ; int X = query ( tree , start , mid , l , r , 2 * node + 1 ) ; int Y = query ( tree , mid + 1 , end , l , r , 2 * node + 2 ) ; return min ( X , Y ) ; } int longestSubArray ( int * A , int N , int K ) { int res = 1 ; int preSum [ N + 1 ] ; preSum [ 0 ] = A [ 0 ] ; for ( int i = 0 ; i < N ; i ++ ) preSum [ i + 1 ] = preSum [ i ] + A [ i ] ; int tree [ 4 * N + 5 ] ; build ( tree , A , 0 , N - 1 , 0 ) ; for ( int i = 0 ; i < N ; i ++ ) { int start = i ; int end = N - 1 ; int mid ; int max_index = i ; while ( start <= end ) { mid = ( start + end ) / 2 ; int min_element = query ( tree , 0 , N - 1 , i , mid , 0 ) ; int expected_sum = ( mid - i + 1 ) * min_element ; int actual_sum = preSum [ mid + 1 ] - preSum [ i ] ; if ( actual_sum - expected_sum <= K ) { start = mid + 1 ; max_index = max ( max_index , mid ) ; } else { end = mid - 1 ; } } res = max ( res , max_index - i + 1 ) ; } return res ; } int main ( ) { int arr [ ] = { 1 , 7 , 3 , 4 , 5 , 6 } ; int k = 6 ; int n = 6 ; cout << longestSubArray ( arr , n , k ) ; return 0 ; }