we have 2 arrays in sorted order, no duplicates
we need find the max continuous length AP [arithmetic prog] in the first array by adding 0 or more elements from the second array
example,
A= [4,8,13]
B=[0,12,9]
ANSWER = [0,4,8,12] , 4
Constraints
n<=1000
Values are <=10000
Combine both the sorted arrays, and then find the maximum AP like LIS
no, wont work. you dont have to add all elements of b in a
Does the question explicitly say we can’t use all the values of array B.
No, what is meant is that we don’t have to all all the elements.
For instance
A=[2,4,6,8]
B=[3]
If we choose to ignore B we get answer as 4, but if we add b answer will be 3
My aproach:
Make a directed graph of values that can be placed next to each other then process in smallest to largest value order and for each store the (common_difference, max_len)
How will you choose what values can be placed then to each other?
then process in smallest to largest value and for each store the (common_difference, max_len) what do you mean by this
Let me tell you a very simple O(n^3) solution which will easily work for sure and can be easily understood .
Array A : [1,4,5,8,9]
Array B : [2,7,10,15]
1) Merge both the arrays. Result : [1,2,4,7,8,9,10,15]
2) Now, just check all pairs in O(n^2) , these pairs are nothing but the first two elements of the A.P we want to end up with!
3) Say, the pair selected is (i,j) (in the merged array(i<j)), if i element is from array B and j is from A , make sure that B element just comes before that A element only in the merged array, or else it will become invalid , not form a continuous subarray which you want.
4) Similarly, check cases when (i,j) : (A,B) , (B,B) , (A,A) , (B,A) accordingly.
5) Now that you have the first two elements of your A.P. : x1 and y1 , common difference , d = y1-x1, now, just check, how many more elements of the form of y1 + k*d are available in your array… k=0 till where you can reach. That’s the largest length of A.P. sequence for pair (i,j) if they are considered as the first two elements of the A.P. Maximum of all the pairs is your final answer.
6) This O(n^3) can be converted to O(n^2) by D.P. Will explain it once you get the above ideas of mine.
okay cool
Dynamic-Programming-Approach :
So, lets say D[i][j] means the longest A.P. length you can get for the pair (i,j) (if (i,j) are the starting 2 elements of your A.P.). I talked about it above as well…
Now, feel (i,j) properly, you know that i<j in the merged array.
Lets assume 3rd element of this A,P. to be k , so it looks like : (i,j,k)
What if you know D[j][k] already ? (calculated before only by DP)
Then, D[i][j] = 1 + D[j][k] , agreed ?
You just need to find such a ‘k’ , then your job is done!!!
(We do that by fixing a j)
Say , merged array looks like this : AABBBBBABBBBBBABB......
So, mergedarray[8]= A, fix j = 8.
Now, find i and k , such that x[i] + x[k] = 2*x[j] , do i=j-1 and k=j+1,
if you see, x[i] + x[k] > 2*x[j] , do , i--, if you see x[i] + x[k] <2*x[j] , do
k++,
as soon as you find
,
x[i] + x[k] = 2*x[j] , you are done ! Voila! You found a valid (i,j,k) ,
so D[i][j] = D[j][k] + 1 ,
make sure your 'i' is allowed to traverse from (2,7) and k is only allowed to travel from (9, 15) .
Finally, the maximum
value of D[i][j] in your dynamic programming table is the answer.
Hope it helps! @vai53
Make an array of size sz = 10000 and mark all the elements present in both the arrays. Since elements are distinct we can safely combine the arrays. So now let’s fix the starting element say x. Now let’s say we know the common difference d, how to find maximum length of AP?
Well you can just check if x, x+d,x+2*d… are there and find maximum l such that x+l*d is present. Then you have a length of (l+1). So how much time it takes? Well is looks \frac{10000}{d} but since there are 2*n elements only it is \frac{2*n}{d}(As soon as you encounter x+l*d is not there you break). Similarly, x can take only 2*n values but d can take values in range [1, 10000]. So just iterate on all possible values. Therefore complexity is: O(2*n*max(A_i, B_i)*log(2*n)). Note that this is an upper bound only. My intuition is that it would run in O(2*n*max(A_i, B_i)) with some small constant, that is log(2*n) won’t be there.
Your traversal can be O(n) in worst case making the complexity O(n^3).
Nopes, its O(n^2)
All I need is 2-loops, one for j, which goes from N to 1. And another loop where (i & k), move simultaneously. You may read again, ‘j’ has been fixed, I am not searching for all particular (i,j) if thats what you thought.
@samarth2017
Can you present some pseudo-code?
Yup, will write it in sometime. Sure.
@vai53 Here, is the dynamic programming code for the Facebook problem :
CvklP2 - Online C++0x Compiler & Debugging Tool - Ideone.com
Time complexity : O(n^2) , where, n=1000.