python,主要使用单调栈和二分查找来优化
n = int(raw_input())
nums = map(int, raw_input().split())
stk = [nums[0]]
def bound(nums, target):
size = len(nums)
l, r = 0, size-1
while l<r:
mid = l+r>>1
if nums[mid]>=target:
r = mid
else:
l = mid+1
return l
res = 1
for i in range(1, n):
if len(stk)>0 and nums[i]>stk[-1]:
stk.append(nums[i])
res +=1
else:
index = bound(stk, nums[i])
stk[index] = nums[i]
print res