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
