Longest Increasing Subsequence

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.

For example, a longest increasing subsequence of

[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

is

[0, 2, 6, 9, 11, 15].

This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not unique: for instance,

0, 4, 6, 9, 11, 15 or
0, 2, 6, 9, 13, 15 or
0, 4, 6, 9, 13, 15

are other increasing subsequences of equal length in the same input sequence.

Solutions

Dynamic Programming

Implementation

class LongestIncreasingSubsequence:
    def solve(self, array):
        lengths = [1 for i in range(len(array))]
        pre_idx, cur_idx = 0, 1
        while cur_idx < len(array):
            if array[pre_idx] < array[cur_idx]:
                cur_len = lengths[pre_idx] + 1
                if cur_len > lengths[cur_idx]:
                    lengths[cur_idx] = cur_len
            pre_idx += 1
            if pre_idx == cur_idx:
                cur_idx += 1
                pre_idx = 0
        return max(lengths)