Longest Increasing Sequence

The Longest Increasing Sequence (LIS) asks for the longest increasing sequence in a list of numbers. For example,  in the list 1, 6, 2, 5, 4, 7, the longest sequence would be 1, 2, 5, 7.

In this case, the greedy algorithm isn’t right, for example, the greedy algorithm in this case would give 1, 6, 7, the length is 3.

That is because the greedy approach will jeopardize the optimal solution by choosing a temporarily ‘best’ solution (and trapped in local optimal).

The Dynamic Programming (DP) can be used to solve this problem. The state transition formula (recursive) is:

for and and
represents the answer up to the i-th number
represents the value of the i-th number.

The above DP equation is easy to write and easy to understand. It gives the general approach (divide and conquer) to split the problem into its smaller forms. The answers of each sub-problems are also part of the global optimal (part of the link) i.e. considering the shortest distance between three nodes, A, B and C. If the shortest path between A and C passes B, then the path between A and B or B and C must also be the optimal otherwise, it can be replaced and a better/shorter path will be found.

The Python solution to generate this solution is given below, which yields complexity.

#!/usr/bin/env python

seq = [1, 7, 3, 5, 9, 4, 8]
f = len(seq) * [1]

for i in xrange(len(seq)):
    for j in xrange(i):
        if seq[j] < seq[i] and f[j] >= f[i]:
            f[i] = f[j] + 1

print max(f)

–EOF (The Ultimate Computing & Technology Blog) —