Longest Increasing Subsequence from each element

Question

Given a list {x_i}, I want to find the longest increasing subsequence starting from each element such that the starting element is included in the subsequence.

The obvious way would to do this would be to perform the usual longest increasing subsequence algorithm on each element, giving O(n^2 logn). Can this be beaten?

Answer 1

You can use DP and bring it down to O(n^2).

Let the input be x1, x2, ..., xn

Let f1, f2, ..., fn be the length of longest increasing sequence starting from ith element. Initialize all of them to 1.

Now,

for i = n-1, n-2, .... , 1:
    for j = i,i+1,...,n:
        if x[i]<x[j]:
            fi=max(fi, fj+1)

If you want actual sequence in addition to the length, keep track of another variable g1,g2, ..., gn where gi is the next element to follow. Initialize gis to NULL.

for i = n-1, n-2, .... , 1:
    for j = i,i+1,...,n:
        if x[i]<x[j]:
            if fi<fj+1:
                fi=fj+1
                gi=j

Once you have gs, I will leave you to figure out how to enumerate the sequence starting from a particular location.