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