LIS问题：
求数组A[i]的最长（严格）上升子序列的元素个数。

先看一看O(n²)的动态规划算法，定义d[i]为以A[i]作为结尾的LIS长度，则d[i]=max{d[j]+[A[i]>A[j]]}(j<i),边界是d[0]=1，答案是d[n-1]。由于每次都要枚举比i小的所有j，所以时间复杂度是O(n²)的。

每个d[i]的计算，会用到所有的d[j](j<i)，我们注意到如果这之中有d[j1]==d[j2]==...==d[jk]的一系列j，我们只需要用到它们对应的A[j1]、A[j2]、...、A[jk]值最小的那一个。所以对于d[j]相同的一系列下标，我们只保留1个。

所以我们建立d的值到下标的映射f:x→j，即f[x] = (满足d[j]==x的j中A[j]最小的j)，对于当前还不可行的x，令f[x]=∞。对于任意可行的x0，1、2、...、x0-1一定也都是可行的。

假如有了映射f，计算d[i]时就依次查看f[i]、f[i-1]、f[i-2]、...、f[1]的值，找到第一个满足A[f[k]]<A[i]的k，就有d[i]=k+1。但是f[x]不一定是单调的，所以没办法快速查找，于是我们建立映射g，g[x]=A[f[x]]，g[x]的定义比较绕：满足d[j]==x的j中A[j]最小的j的A[j]值，可以证明它是单调的。

假如有了映射g，计算d[i]时就查找最大的k使得g[k]<A[i]，就有d[i]=k+1，由于g是单调的，所以可以二分查找。

按照上面那样算完d[i]后，我们需要维护g，g[1]、g[2]、...、g[k]不需要更新，因为A[i]比这些值要大，A[i]的出现并没有使得它们可以以更小的元素作为结尾，g[k+2]以及之后的g不需要更新，因为A[i]虽然小于等于这些值，但以A[i]结尾的LIS也就是k+1的长度，g[k+2]中存的是LIS长度为k+2的序列中结尾的最小值。只需要更新g[k+1]=A[i]，因为以A[i]结尾的LIS长度为k+1，且g[k+1]>=A[i]。