### 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 (10^{6}).

### QUICK EXPLANATION:

Since sum of all the elements is restricted to be less than **10 ^{6}**, 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.