# PROBLEM LINK :

Practice

Contest

**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 is *O(Q*N^2)* as each time LIS calculation takes *O(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 is *O(N^2 + Q)*.It will easily pass in time limit.Also,there is better approach to find LIS in *O(NlogN)*.So, we can also solve this problem in
*O(NlogN + Q)*.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found Link

Tester's solution can be found Link

asked
**26 Aug '17, 12:29**

4★manjunath1996

128●7

accept rate:
8%