CODEWITHSUNDEEP
dynamic-programming
user926958
user926958

Reputation: 9565

How to find the actual sequence of a Longest Increasing Subsequence?

This is not a homework problem. I am reviewing myself of the Longest Increasing Subsequence problem. I read every where online. I understand how to find the "length", but I don't understand how to back-trace the actual sequence. I am using the patience sorting algorithm to find the length. Can anyone explain how to find the actual sequence? I do not really understand the version in Wikipedia. Can someone explain in a different method or different way?

Thanks.

Upvotes: 2

Views: 1181

Answers (2)

Óscar López
Óscar López

Reputation: 235984

This Python code solves the Longest Increasing Sequence problem, and also returns one of such sequences. The trick is, at the same time that the dynamic programming table gets filled, another array is also filled, storing the index of the elements that were used to construct the optimal solution.

def an_lis(nums):
    table, solution = lis_table(nums)
    if not table:
        return (0, [])
    n, maxLen = max(enumerate(table), key=itemgetter(1))
    lis = [nums[n]]
    while solution[n] != -1:
        lis.append(nums[solution[n]])
        n = solution[n]
    return lis[::-1]

def lis_table(nums):
    n = len(nums)
    table, solution = [0] * n, [-1] * n
    for i in xrange(n):
        maxLen, maxIdx = 0, -1
        for j in xrange(i):
            if nums[j] < nums[i] and table[j] > maxLen:
                maxLen, maxIdx = table[j], j
        table[i], solution[i] = 1 + maxLen, maxIdx
    return (table, solution)

Upvotes: 0

Bartolinio
Bartolinio

Reputation: 790

Lets define as max(j) as the longest increasing subsequence up to A[j]. There are two options: or we use A[j] in this subsequence, or we don't.

If we dont use it, then the value will be max(j-1). If we do use it, then the value will be max(i)+1, when i is the biggest index such that i < j and A[i] < A[j]. (Here we assume that the max(i) sequence uses i- not neccessary true, but we can solve this issue by saving for each cell 2 values- the max(j) value, and max*(j), when max*(j) is the longest increasing subsequence up to A[j] that uses A[j]. max*(j) will be calculated each time as max*(i)+1).

To sum up, the recursive formula for calculating max(j) will be: max{max(j-1),max*(i)+1},and max*(j)= max*(i)+1. In each array cell you can save a pointer, that tells you if you chose to use the A[j] cell or not. In this way you can find all the sequence while moving backwards on the array.

Time Complexity: The complexity of the recursive formula and finding the sequence at the end is O(n). The problem here is finding for each A[j] the corresponding A[i] such that i is the biggest index such that i < j, A[i] < A[j]. Of course you can do it naivly in O(n^2) (from each cell go backwards until you find this i). If you want to do better then I'm pretty sure that you can do it in O(nlogn) in the following way:

*Sort your Array. 1) go for the smallest integer in the array, and notate is position in the array as k.

2)For A[k+1], we have of course A[k] < A[k+1]. If A[k+1]>A[k+2] then k will feet to the k+2 cell as well, and so on until we have A[k+m] < A[k+m+1], and then k+m is feet to k+m+1,

3)delete all the cells that you found thier corresponding cell in the previous stage

4) return to 1.

Hoped that it help. Please notice that I thought about it all alone, therefore there is a very small chance that there is some mistake here- please be convinced that I'm right and ask for more clarifications, if you need.

Upvotes: 1

Related Questions