Maximum length of same indexed subarrays from two given arrays satisfying the given condition | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxLength ( int a [ ] , int b [ ] , int n , int c ) { if ( n == 0 ) return 0 ; int max_length = 0 ; int low = 0 , high = n ; while ( low <= high ) { int mid = low + ( high - low ) / 2 ; if ( possible ( a , b , n , c , mid ) ) { max_length = mid ; low = mid + 1 ; } else high = mid - 1 ; } return max_length ; } bool possible ( int a [ ] , int b [ ] , int n , int c , int k ) { deque < int > dq ; int sum = 0 ; for ( int i = 0 ; i < k ; i ++ ) { sum += a [ i ] ; while ( dq . size ( ) > 0 && b [ i ] > b [ dq . back ( ) ] ) dq . pop_back ( ) ; dq . push_back ( i ) ; } int total_cost = sum * k + b [ dq . front ( ) ] ; if ( total_cost <= c ) return true ; for ( int i = k ; i < n ; i ++ ) { sum += a [ i ] ; sum -= a [ i - k ] ; while ( dq . size ( ) > 0 && dq . front ( ) <= i - k ) dq . pop_front ( ) ; while ( dq . size ( ) > 0 && b [ i ] > b [ dq . back ( ) ] ) dq . pop_back ( ) ; dq . push_back ( i ) ; total_cost = sum * k + b [ dq . front ( ) ] ; if ( total_cost <= c ) return true ; } return false ; } int main ( ) { int A [ ] = { 1 , 2 , 1 , 6 , 5 , 5 , 6 , 1 } ; int B [ ] = { 14 , 8 , 15 , 15 , 9 , 10 , 7 , 12 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int C = 40 ; cout << maxLength ( A , B , N , C ) ; return 0 ; }