Maximum length of same indexed subarrays from two given arrays satisfying the given condition | 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 ; Finds the maximum element in each window of size k ; Check for window of size K ; For all possible subarrays of length k ; Until deque is empty ; Calculate the total cost and check if less than equal to c ; Find sum of current subarray and the total cost ; Include the new element of current subarray ; Discard the element of last subarray ; Remove all the elements in the old window ; Calculate total cost and check <= c ; If current subarray length satisfies ; If it is not possible ; Driver Code
def maxLength ( a , b , n , c ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT max_length = 0 NEW_LINE low = 0 NEW_LINE high = n NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = int ( low + ( high - low ) / 2 ) NEW_LINE if ( possible ( a , b , n , c , mid ) ) : 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 dq = [ ] NEW_LINE Sum = 0 NEW_LINE for i in range ( k ) : NEW_LINE INDENT Sum += a [ i ] NEW_LINE while ( len ( dq ) > 0 and b [ i ] > b [ dq [ len ( dq ) - 1 ] ] ) : NEW_LINE INDENT dq . pop ( len ( dq ) - 1 ) NEW_LINE DEDENT dq . append ( i ) NEW_LINE DEDENT total_cost = Sum * k + b [ dq [ 0 ] ] NEW_LINE if ( total_cost <= c ) : NEW_LINE INDENT return True NEW_LINE DEDENT for i in range ( k , n ) : NEW_LINE INDENT Sum += a [ i ] NEW_LINE Sum -= a [ i - k ] NEW_LINE while ( len ( dq ) > 0 and dq [ 0 ] <= i - k ) : NEW_LINE INDENT dq . pop ( 0 ) NEW_LINE DEDENT while ( len ( dq ) > 0 and b [ i ] > b [ dq [ len ( dq ) - 1 ] ] ) : NEW_LINE INDENT dq . pop ( len ( dq ) - 1 ) NEW_LINE DEDENT dq . append ( i ) NEW_LINE total_cost = Sum * k + b [ dq [ 0 ] ] NEW_LINE if ( total_cost <= c ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT return False 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 N = len ( A ) NEW_LINE C = 40 NEW_LINE print ( maxLength ( A , B , N , C ) ) NEW_LINE