Given an unsorted array of integers, find the length of longest increasing subsequence. For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

max-seqs.py

array = [10, 9, 2, 5, 3, 7, 101, 18, 31, 25, 68, 45, 12]


# O(n^2)
def longest_seqs(seqs):
    l = []
    for i in range(len(seqs)):
        l.append(max([l[j] for j in range(i) if l[j][-1] < seqs[i]] or [[]],
                     key=len) + [seqs[i]])
    return len(max(l, key=len))


print longest_seqs(array)


# O(nlogn)
def bin_search(num, k, b):
    low = 0
    high = k
    while (low <= high):
        mid = int((low + high)/2)
        if num >= b[mid]:
            low = mid + 1
        else:
            high = mid - 1
    return low


max_seq = 1
k = 0
length = len(array)
b = [0] * length
b[0] = array[0]
for i in range(length):
    if array[i] > b[k]:
        k += 1
        b[k] = array[i]
    else:
        index = bin_search(array[i], k, b)
        b[index] = array[i]

print k + 1