最长增量子序列(Longest Increasing Subsequence )是n个序列的最长单调递增子序列。 例如，a=[1、3、6、7、9、4、10、5、6]的LIS为1 3 6 7 9 10。 我们现在想编程求出所给的数组。 我们可以得到LIS的长度。
关于LIS的求解方法，也有很多使用DP算法的文章，时间的复杂度是o(n2 )。 下面是一个算法，它只需要少于15行的Python或Java代码来实现复杂度o ) O(nlogn )。
假设tails是存储在tails[i]中的数组，是长度为i 1的所有增加子序列的最小末尾元素。
例如，假设nums=[4、5、6、3]，则所有递增子序列如下：
#长度为1[4]、[5]、[6]、[3]=tails[0]=3#长度为2 [ 4，5，6 ]、[ 4，6 ]=tails [1]=5#长度为3 [ 4，4 ]
很容易证明tails是递增的数组。 首先，tails[0]必须是所有元素中最小的数字min1。 因为在长度为1的子序列中，最后最小的数字是序列中最小的数字。 同样，在长度为2的子序列中，最后最小的子序列的最后一个元素必须大于min1。 首先，所有长度为2的增加子序列，因为第二个元素必须大于第一个元素。 如果长度为2的子序列中，一个子序列的最后一个元素小于min1，则在第一个操作中将该元素更新为min1。 对于长度为3的子串，假定前面的tails已经存储前两个末尾的最小数量[a，b]，如果长度为3的子串末尾的数字c3小于b，即[c1，c2，c3]是增加子串且c3 b，则为增加子串这样，前面的结论b与长度为2的增加子串末尾的最小要素矛盾。 因此，这种分步反证法很容易证明tails一定是递增的数组。 那么，在二分查找中，可以很容易地找到需要用tails数组更新的数量。
每次遍历数组nums时，只需执行以下两个步骤之一：
如果x大于所有tails，并且x表示可以位于最长子数组的末尾以形成新的自我承诺，则应用他；如果最长子数组的长度增加1，则tails[i-1] x=tails[i]，则x增加
如果以这种方式维护tails变量，最后的答案就是这个长度。 Python代码如下：
deflengthoflis(self，nums ) :tails=[0]*len ) nums ) size=0 for x in nums: i，j=0，size while i！=j:m=(Ij )/2 if tails [ m ] x : I=m1 else : j=m tails [ I ]=xsize=max (i1，size )返回大小的具体示例tails=[ 3，0，0，0，0 ]
1. x=3，在这种情况下i=0，直接tails[0]=3，tails=[ 3，0，0，0 ]。 表示到目前为止长度为1的增量子序列的末尾最小为3。
2. x=4，这个时候I！=j，但x大于tails的末尾，仍然是另一个tail[1]=4，tails=[ 3，4，0，0 ]。 表示到目前为止长度为1的增量子序列的末尾最小为3，长度为2的增量子序列的末尾最小为4。
3. x=7，大于tails末尾，直接取tails[2]=7，tails=[ 3，4，7，0 ]。 说明到目前为止长度为1的增量子序列的末尾最小为3，长度为2的增量子序列的末尾最小为4，长度为3的增量子序列的末尾最小为7。
4. x=2，在这种情况下，x小于tails的末尾，因此必须在两分钟内找到大于x的最小数量。 在tails中找到大于2的最小数量为3，更新tail[0]=2。 此时，tails=[2、4、7、0、0]。 说明到目前为止长度为1的增量子序列的末尾最小为2，长度为2的增量子序列的末尾最小为4，长度为3的增量子序列的末尾最小为7。 该步骤的理解很重要，[ 2，4，7，0，0 ]的存在并不意味着到目前为止的增加子序列是2、4、7，而是长度分别为1、2、3的增加子序列当前得到的最小的终端要素是2、4、7 其目的是通过保留tails中的元素，使与长度为i 1的子序列相对应的tails[i]元素每次最小化，并出现新元素以替换以前的值。 这是“在我面前形成了长度为m的增量序列，而你们的长度是
m这个序列的末尾最大的一个数比我还大，不如把我和末尾最大的那个元素换一下，这样你看咱们还是一个递增序列，长度也不变，但是我和你们更亲近”。别的元素一听是这么个道理啊，于是就踢出最后一个元素，换上了这个新的更小的元素。在元素2还没进入的时候，形成的状态是这样的，我们从正面看就是我们得到那个tails数组，其实每个数组对应一个相应的递增序列，也就是从左侧或者右侧看得到的实际的递增序列。下面元素2进入：
因为2比3小，所以能够形成的长度为1的最小的递增子序列是2。其余不变。
x = 5， 通过比较，5比7小，比4大。发生替换：
通过这个图我们也能很直观的看出来，此时的tails数组变成了[2, 4, 5, 0, 0]，而相应的长度为1，2，3的最小递增数组分别为[2], [3, 4], [3, 4, 5]。这样，如果再进入一个6，就直接放在5的后面，递增数组长度+1；反之，如果进来的是个1，就替换掉2。通过维护这样一个tails数组，我们就能够很方便的求出递增子序列的最大长度了。递增子序列的最大长度也就是当前tails数组中所能到达的最右侧的位置。
而这种方法通过二分查找，时间效率只有O(nlogn)，空间效率最坏情况也是O(n), 只需要维护一个长度为n的tails数组即可。
如果需要求的是非严格单调递增数组，只需要把if tails[m] < x:改为if tails[m] <= x:即可。
JAVA
public int lengthOfLIS(int[] nums) { int[] tails = new int[nums.length]; int size = 0; for (int x : nums) { int i = 0, j = size; while (i != j) { int m = (i + j) / 2; if (tails[m] < x) i = m + 1; else j = m; } tails[i] = x; if (i == size) ++size; } return size;}// Runtime: 2 ms