Constrained Longest Increasing Subsequence

Question

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(N²log(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.

Answer 1

The canonical dynamic program for LIS computes, for each k, the longest increasing subsequence of the elements at index 1..k that includes the element at index k. Using this data and the mirror image data for longest increasing subsequences of k..n, we find the LIS that includes index k as the union of the longest before k and the longest after k.

O(n log n)

Answer 2

Having an index i that must be in the subsequence makes it an easy task to look to the left and right and see how far you can go to remain strictly increasing. This will take at most O(N) steps.

The straight forward solution will now just repeat this for all N values at the index i, which gives a total effort of O(N^2).

But note, that when changing the value at index i, the calculations done earlier can be reused. It is only necessary to check if the the sequence can be extended beyond i in either direction or not, If yes, you know already how far (or can calculate it now once and for all).

This brings the total effort down to O(N).