Given an array A[0]...A[n-1] of integers, find out the length of the longest ascending subsequence.

Assumptions:

A is not null

Examples:

Input: A = {5, 2, 6, 3, 4, 7, 5}
Output: 4
Because [2, 3, 4, 5] is the longest ascending subsequence.

class Solution(object):
  def longest(self, array):
    if len(array) < 1:
      return 0
    tails = [0] * len(array)
    size = 0
    for x in array:
      i,j = 0,size
      while i < j:
        m = (i + j)/2
        if tails[m] < x:
          i = m + 1
        else:
          j = m
      tails[i] = x
      size = max(i+1,size)
    return size