The Classic LIS Problem

The Classic LIS Problem

In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. wiki

For example, the longest increasing subsequence(LIS) of array [2,3,1,6,9] is [2,3,6,9]. The LIS of array [7,8,9,1,2,3,4] is [1,2,3,4].

LIS can be solved using dynamic programming. There are two methods using DP, one is more intuitive, the other is more efficient.

Intuitive Solution

Given an array of [a0, a1, a2,...,an], define that d[i] is the length of LIS which is ended with ai. Then d[i] should be the in one of the below two case:

  • only choose the ai with length 1.
  • choose the maximum from d[j] + 1 where j < i and a[j] < a[j].

So we can define the deduction formula: d[i] = max(1, {d[j]+1 | j<i, d[j]<d[i]}).

Using this formula, we can calculate from bottom up, say from d[0] to d[n], from which we get the largest one for result. Below is the python program that express this process.

def lis_solution_1(arr):
    best, best_arr = -1, []
    d, d_arr = [], []
    length = len(arr)
    # initialization
    for i in range(length):
        d.append(0)
        d_arr.append(0)
    # dp, update array d from bottom up
    for i in range(length):
        tmp = -1
        tmp_arr = []
        for j in range(i):
            if arr[j] < arr[i] and tmp < d[j] + 1:
                tmp = d[j] + 1
                tmp_arr = d_arr[j][:]
        if tmp > 1:
            d_arr[i] = tmp_arr[:]
            d_arr[i].append(arr[i])
            d[i] = tmp
        else:
            d_arr[i] = [arr[i]]
            d[i] = 1
        if best < d[i]:
            best = d[i]
            best_arr = d_arr[i]
    return best, best_arr

Since there are two for loop in program, it's time complexity is O(n*n). In addition, we need to store the LIS array for every index i, we also need O(n*n) space.

More Efficient One

Another idea is to define d[i] as the smallest number of all increasing subsequences of length i+1.

For example, for i == 0, it means in all increasing subsequence of length 1, find the smallest one, and assign it to d[0]. If there is no increasing subsequence of a specific i, then d[i] should be assigned to INF, which means no such subsequence.

At last, we need to find out the largest i so that d[i] is not INF, it means the length of longest increasing subsequence is i+1.

Below is the python program that demonstrate this process.

def lis_solution_2(arr):
    def binary_search(arr, begin, end, target):
        while begin <= end:
            middle = (begin + end) / 2
            if arr[middle] < target:
                begin = middle + 1
            else:
                end = middle - 1
        return begin

    INF = 1000000
    length = len(arr)
    d = []
    # initialization
    for i in range(length):
        d.append(INF)
    # update array d
    last_index = -1
    for i in range(length):
        index = binary_search(d, 0, last_index, arr[i])
        d[index] = arr[i]
        last_index = max(last_index, index)
    # find out the lis length
    ans = 0
    for i in range(length):
        if d[i] == INF:
            break
        ans = i

    return ans+1

Here, every time we update the array d, we use binary search to locate the index which should be updated, so the time complexity is O(nlogn). But this method may not easy to give out the elements of the LIS, since the element maybe overwritten when we update the array d.

For the input array [7,8,9,1,2,3,4], the array d is updated as below.

[1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000]
[7, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000]
[7, 8, 1000000, 1000000, 1000000, 1000000, 1000000]
[7, 8, 9, 1000000, 1000000, 1000000, 1000000]
[1, 8, 9, 1000000, 1000000, 1000000, 1000000]
[1, 2, 9, 1000000, 1000000, 1000000, 1000000]
[1, 2, 3, 1000000, 1000000, 1000000, 1000000]
[1, 2, 3, 4, 1000000, 1000000, 1000000]
Currently unrated

Comments

ADDRESS

  • Email: jimmykobe1171@126.com
  • Website: www.catharinegeek.com