0

Maximum length of same indexed subarrays

Difficulty: MEDIUM
Contributed By
Ankush Gupta

Problem Statement
Suggest Edit

Given two arrays ‘A’ and ‘B’ and an integer ‘C’, the task is to find the maximum possible length, say K, of the same indexed subarrays such that the sum of the maximum element in the K-length subarray in ‘B’ with the product between K and sum of the K-length subarray in ‘A’ does not exceed ‘C’.

More Formally you have to find the maximum length subarray, which starts and end at the same point in ‘A’ and ‘B’, and the sum of, maximum element of ‘B’ in that subarray, with the product of the length of the subarray and sum of a subarray in ‘A’ is less than or equal to ‘C’.

For example

Given:
‘N’ = 6, ‘C’ = 23
‘A’[] = {5, 19, 13, 2, 4, 0} 
‘B’[] = {10, 4, 7, 4, 5, 14}
The max-length subarray will be 2, consider the subarray from 3 to 4 (0-based indexing) and here, the subarray sum of ‘A’ = 6 max element in ‘B’ = 5. Therefore 6*2 + 5 = 17, Which is less than 23. Hence 2 is the final answer. 

If there are multiple answers, you can choose any subarray.

Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘N,’ where ‘N’ is the number of elements of the array and ‘C’ where ‘C’ is the given integer.

The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.
Output Format :
For each test case, You are supposed to return an integer that denotes the maximum length subarray.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘N’ <= 5000
0 <= 'ARR[i]’ <= 10 ^ 6

Time Limit: 1sec.

Sample Input 1 :

2
6 23
5 19 13 2 4 0 
10 4 7 4 5 14 
5 46
15 18 2 18 3 
14 15 9 19 1 

Sample Output 1 :

2
1  

Explanation of the Sample Input 1:

In the first test case, The max-length subarray will be 2, consider the subarray from 3 to 4 (0-based indexing), and here, the subarray sum of ‘A’ = 6 max element in ‘B’ = 5. Therefore 6*2 + 5 = 17, Which is less than 23. Hence 2 is the final answer. 

In the second test case, The max-length subarray will be 1, consider the subarray from 2 to 2 (0-based indexing), and here, the subarray sum of ‘A’ = 2 max element in ‘B’ = 9. Therefore 2*2 + 9 = 13, Which is less than 46. Hence 1 is the final answer. 

Sample Input 2 :

2
6 36
4 17 12 16 5 12 
1 10 4 14 13 8 
5 16
3 4 13 0 9 
19 16 16 17 19

Sample Output 2 :

1
0
Reset Code
Full screen
copy-code
Console