Consider an array, which has N
integers. Now we are given with an index i
, which can take up values from 1
through N
. This particular index should always be present in the LIS that we generate. Calculate the LIS for each value at i
.
How can we solve the above problem efficiently? My straightforward solution is to vary the index i
for all of its values and calculate LIS. The time complexity goes up to O(N2log(N)). Can it be beaten?
Example:
N = 2. i = 1
Say the given array is [1,2].
[1,2]
or [2, 2]
The longest (strictly) increasing subsequence in each case is 2
and 1
.