主题说明：
查找数组最长的增量子序列的长度
例如，ARR=[2、1、6、4、5、2、7、4]
那么)函数返回4。 因为(1、4、5、7 )或) 2、4、5、7 )是最长的增加子序列，长度为4。
[ leet代码300 ] https://leet代码.com/problems/longest-increasing-subsequence /
方法1:o(n^2) )。
算法流程：
使用数组h[]。 其中h[i]表示原始数组以arr[i]结尾的最长增量子序列的长度。
将i=0至i=n-1的过程重复n次，求出h=[1、1、2、1、3、2、4、3]。 求h[i]时，需要考察小于I的j。 对于arr[i]arr[j]，h[i]必须至少为h[j] 1。 这样，在前一次遍历之后就可以知道h[i]。
求出的各元素后，扫描求出最大即可。
算法原理：
由于原始数组的最长增量子序列始终结束于原始数组中的某个位置，因此，如果获得结束于数组中每个位置的最长增量子序列，则会获得这些“最长”中的最大值。 求各位置的最大时，由前面位置的要素和最长子系列的长度决定。 如果一共求n次，每次都需要遍历上一个，所以复杂度为o(n^2)。
算法代码：
publicintlengthoflis(int[]nums ) {
if(nums==null||nums.length==0) () ) ) ) ) ) ) ) )。
返回0；
int[] h=new int[nums.length]；
for(intI=0； I
int max=0；
for(intj=0； Jj
if(nums[I]nums[j] ) {
max=math.max(h[j]，max )；
}
}
h[i]=max 1；
}
int max=0；
for(intI=0； I
if(h[I]max ) ) )。
max=h[i]；
}
返回最大值；
}
方法2:o(nlog(n ) )
算法流程：
使用数组h，首先假设h[0]=arr[0]。 以已经代入的h前面的部分为有序区，只考察有序区。
接下来进行遍历，相对于arr[i]，在h的有序区域中寻找大于第一个arr[i]的位置。 如果找到，则将该位置的值更新为arr[i]。 否则，h有序区域的长度将增加1，新位置的值为arr[i]。 使用二分查找位置
在上述过程中，从位置0到arr[i]更新位置的元素的数目是以arr[i]结束的最长增加子序列的长度。 从两分钟找到的位置就能知道这个长度。 使用全局变量在max存储中更新最长增量子序列的长度。
算法原理：
h[i]扫描到当前时刻，表示长度为i 1的最长递增部分序列的最小末尾。 这样，我们每次进行的工作要么增加最长的增加子序列的长度，要么不改变长度，但是更新了与各长度对应的最小末尾。 这是因为你更小。 我后半部分的要素比你更容易变大。 这样地确定最后h的有效区间长度，但为了不继续遍历，更新中途使用max记录当前位置时的最长递增子序列即可。 进行n次，每次将位置log(n )分成2部分进行查找，因此复杂度为n ) log(n )。
算法代码：
publicintlengthoflis(int[]nums ) {
if(nums==null||nums.length==0) () ) ) ) ) ) ) ) )。
返回0；
int[] h=new int[nums.length]；
h[0]=nums[0]；
int max=0； //长子序列的最右边的位置
for(intI=1； I
if(nums[I]h[max] ) {
h[ max]=nums[i]；
继续；
}
else{
intpos=findfirstbigger(h，0，max，nums[i]；
h[pos]=nums[i]；
}
}
返回最大值1；
}
publicintfindfirstbigger (int [ ] h，int left，int right，int target ) {
if(left==right ) )。
返回左；
int mid=(左光线)/2；
if(h[mid]
returnfindfirstbigger(h，mid 1，right，target )；
else
returnfindfirstbigger(h，left，mid，target )；
}