Maximum length of same indexed subarrays from two given arrays satisfying the given condition | Python3 program for the above approach ; Stores the segment tree node values ; Function to find maximum length of subarray such that sum of maximum element in subarray in brr [ ] and sum of subarray in arr [ ] * K is at most C ; Base Case ; Let maximum length be 0 ; Perform Binary search ; Find mid value ; Check if the current mid satisfy the given condition ; If yes , then store length ; Otherwise ; Return maximum length stored ; Function to check if it is possible to have such a subarray of length K ; Check for first window of size K ; Calculate the total cost and check if less than equal to c ; If it satisfy the condition ; Find the sum of current subarray and calculate total cost ; Include the new element of current subarray ; Discard the element of last subarray ; Calculate total cost and check <= c ; If possible , then return true ; If it is not possible ; Function that builds segment Tree ; If there is only one element ; Find the value of mid ; Build left and right parts of segment tree recursively ; Update the value at current index ; Function to find maximum element in the given range ; If the query is out of bounds ; If the segment is completely inside the query range ; Calculate the mid ; Return maximum in left & right of the segment tree recursively ; Driver Code ; Initialize and Build the Segment Tree ; Function Call
import math NEW_LINE seg = [ 0 for x in range ( 10000 ) ] NEW_LINE INT_MIN = int ( - 10000000 ) NEW_LINE def maxLength ( a , b , n , c ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT max_length = int ( 0 ) NEW_LINE low = 0 NEW_LINE high = n NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = int ( low + int ( ( high - low ) / 2 ) ) NEW_LINE if ( possible ( a , b , n , c , mid ) != 0 ) : NEW_LINE INDENT max_length = mid NEW_LINE low = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT high = mid - 1 NEW_LINE DEDENT DEDENT return max_length NEW_LINE DEDENT def possible ( a , b , n , c , k ) : NEW_LINE INDENT sum = int ( 0 ) NEW_LINE for i in range ( 0 , k ) : NEW_LINE INDENT sum += a [ i ] NEW_LINE DEDENT total_cost = int ( sum * k + getMax ( b , 0 , n - 1 , 0 , k - 1 , 0 ) ) NEW_LINE if ( total_cost <= c ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT for i in range ( k , n ) : NEW_LINE INDENT sum += a [ i ] NEW_LINE sum -= a [ i - k ] NEW_LINE total_cost = int ( sum * k + getMax ( b , 0 , n - 1 , i - k + 1 , i , 0 ) ) NEW_LINE if ( total_cost <= c ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT DEDENT return 0 NEW_LINE DEDENT def build ( b , index , s , e ) : NEW_LINE INDENT if ( s == e ) : NEW_LINE INDENT seg [ index ] = b [ s ] NEW_LINE return NEW_LINE DEDENT mid = int ( s + int ( ( e - s ) / 2 ) ) NEW_LINE build ( b , 2 * index + 1 , s , mid ) NEW_LINE build ( b , 2 * index + 2 , mid + 1 , e ) NEW_LINE seg [ index ] = max ( seg [ 2 * index + 1 ] , seg [ 2 * index + 2 ] ) NEW_LINE DEDENT def getMax ( b , ss , se , qs , qe , index ) : NEW_LINE INDENT if ( se < qs or ss > qe ) : NEW_LINE INDENT return int ( INT_MIN / 2 ) NEW_LINE DEDENT if ( ss >= qs and se <= qe ) : NEW_LINE INDENT return seg [ index ] NEW_LINE DEDENT mid = int ( int ( ss ) + int ( ( se - ss ) / 2 ) ) NEW_LINE return max ( getMax ( b , ss , mid , qs , qe , 2 * index + 1 ) , getMax ( b , mid + 1 , se , qs , qe , 2 * index + 2 ) ) NEW_LINE DEDENT A = [ 1 , 2 , 1 , 6 , 5 , 5 , 6 , 1 ] NEW_LINE B = [ 14 , 8 , 15 , 15 , 9 , 10 , 7 , 12 ] NEW_LINE C = int ( 40 ) NEW_LINE N = len ( A ) NEW_LINE build ( B , 0 , 0 , N - 1 ) NEW_LINE print ( ( maxLength ( A , B , N , C ) ) ) NEW_LINE