### PROBLEM LINK :

**Author:** manjunath1996

**Tester:** nmalviya1929

**Editorialist:** manjunath1996

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

DP,LIS

### PROBLEM:

Given an array of N elements and Q queries.Each query consist of and index of array.You have to find length of Longest Increasing Subsequence consisting of element at that index.

### EXPLANATION:

You have to find LIS consisting of element at given index.One brute force approach will be calculating LIS for each query as follows. for all i from 0 to N-1 LIS(i)=1; if(i > query_index) for all index from query_index to i-1 if( a(i)> a(j) ) LIS(i)=max(LIS(i),LIS(j)+1); else for all index from 0 to i-1 if( a(i)> a(j) ) LIS(i)=max(LIS(i),LIS(j)+1); The complexity of this code isO(Q*N^2)as each time LIS calculation takesO(N^2)time. It will give TLE given q=10^5 queries and 10^3 array length. So,one observation we can make is,LIS(i) consist of length of LIS which contains element of that index i.So,We can find Longest Increasing subsequence from left as well as Longest Decreasing Subsequence from right. Now,at every index i,We have LIS(i) which is Longest Increasing Subsequence of subarray [0...i] which consist of element at index i. Also,We have LDS(i) which actually is LIS of subarray[i..n] which contains element at index i. So,To find LIS of whole array which consist of element at index i, we can easily answer it as LIS(i)+LDS(i)-1. The running time isO(N^2 + Q).It will easily pass in time limit.Also,there is better approach to find LIS inO(NlogN).So, we can also solve this problem inO(NlogN + Q).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found Link

Tester’s solution can be found Link