PROBLEM LINK:#
Author : Sergey Nagin
Tester : Kevin Atienza
Editorialist : Triveni Mahatha
DIFFICULTY:#
MEDIUM - HARD
PREREQUISITES:#
Longest Increasing Subsequence
Dynamic Programming
Fenwick Tree / Segment Tree
PROBLEM:#
Given an array, find length of longest increasing sub-sequence in a subarray efficiently for multiple queries. The array obeys additional condition : sum of elements of all the given elements is small (106).
QUICK EXPLANATION:
Since sum of all the elements is restricted to be less than 106, this implies there can not be more than maxNum = 1413 distinct numbers in the given array. Now map down the given numbers in the range 1 to maxNum.
We will do dp to find the answer now. We will start from index 1 of the given array, inp, and iterate, variable i, till we reach the end of it. Let’s define the dp state now. For any index i, dp (val, len) denotes the maximum index j such that length of LIS is len in the subarray inp[j … i] is equal to len and the subsequence ends at value equal to val. It stores -1 if that length is not possible.
dp(val, len) := Max(dp(v, len-1)) for 1 <= v < val. We can use maxNum fenwick trees, it will be helpful to find this maxima efficiently as well as for the update operation.
Apart from this, we will maintain another array ans such that ans[l] denotes the maximum possible index j such that length of LIS starting from that index is greater equal to l. This array can be used to answer all the queries.
Note that we when we reach index, i, we will answer all the queries that ends et i. And this ans array will be useful in answer the queries.
DETAILS:#
AUTHOR’S AND TESTER’S SOLUTIONS:#
Author’s solution can be found here.
Tester’s solution can be found here.