M71LIS- Editorial

general
, ,
1

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

1 Like