1.Given array A of size n.A triplet i,j,k is interesting if for evey i<p<j A[p]<A[i] and A[p]<A[j] and for every j<q<k A[q]<A[j] and A[q]<A[k]. Among all such interesting triplets find the maxium distance between k and i.(N<1e5) (Google)

2.An array of size n can have 3 values lets call them A,B,C.There are R requirements which demands exactly zi distinct values between xi and yi ,all these are of course input for R lines. How many such arrays are possible N<=300,R<=300 (Rubrik)

Can anyone give some ideas to approach these questions.

make 2 arrays val_left and val_right representing the leftmost and rightmost element bigger than current element (-1 if any element does not satisfy the case )

now use 2 pointer from both sides, such that val_left[L] and val_right[R] is non -1 value

now compute max bw elements at index L and R (both exclusive) — if max is greater than both elements (at L and R) you got the answer

else whichever element is bigger than that max, update it with next possible answer (L++ or R-- such that new value of L and R is non -1)

in Q2 you are probably saying elements of array can only have 3 possible values and 1<=zi<=3

we know that priority of zi=1>zi=2>zi=3

so we will maintain a priority array with max priority stored corresponding to any index

lets say xi to yi demand zi=2

so in priority array from xi+1 to yi update min value of zi i.e. priority[i] = min(priority[i],zi)

now a simple dp problem

dp[0]=1;

for i in 1 to N

dp[i]=dp[i-1]*priority[i]

I think it fails for some test cases :

like consider xi,yi,zi as[(1,4,1),(4,6,3),(6,8,1)] your array will be [1,1,1,1,3,1,1,1] and gives answer as 3 but answer would be 6 right...?

no

the array will be [3,1,1,1,3,3,1,1]

and the answer will be 27

[A|B|C]^4 + [A|B|C] + [A|B|C]^3