求最长递增子序列的长度

一，问题描述

给定一个没有负数的序列，求解它的最长 递增 子序列 的长度。比如： arr[] = {3,1,4,1,5,9,2,6,5,3,9}  的最长递增子序列长度为4。即为：1,4,5,9

二问题分析

拿到这个问题的时候我首先想到的暴力解法，我先假设以每一个数开头的序列能有多长，比如我以3为开头最长能多长、以1开头能有多长。举个例子先定义一个变量max=0记录最长子序列的长度先从数组第一个数开始遍历3 依次遍历数组最长子序列长度。这是暴力解法时间复杂度就是O（n^2)。

三、前方高能！！！！

下面我就介绍一个时间复杂度O（nlogn)的算法，上面我讲的那个算法虽然是一个最简单最直接的算法也体现了人的自然智慧。但是实现起来真的比较复杂多个判断语句而且空间复杂度还是O（n）。所以我讲一个时间复杂度O（nlogn)，为什么是O（nlogn)而不是O（n^2）呢，说到这里有不少小伙伴想到了二分了把，每次时间复杂度为O（logn）我的第一想法也是二分，那么要怎么把这二分运用到求最长递增子序列中尼？

这时候我们不要以刚刚最直接的思想去想这个问题，我们反过来想这个问题。那我们就假设以数组中的一个数为这个最长子序列的长度的结尾，判断它能否成为这个序列的结尾，如果在这个序列中找不到任何一个数比这个数大，那么这个数能成为序列的结尾，依次遍历就能找到最长的子序列。

先设一个数组为d 数组d[i]表示第长度为i+1的子序列最小结尾是d[i]，所以就把d[0]=a[0]先放进去，然后依次遍历找比第一个比a[i]大的数，如果找不到就说明该数可以作为子序列，子序列加一。这个时候二分就能在这里用上。

代码：