开发笔记:POJ2533LongestOrderedSubsequence[最长递增子序列长度][LIS问题]

题目链接：http://poj.org/problem?id=2533

Time Limit: 2000MS Memory Limit: 65536K

Description

Input

Output

Sample Input

7
1 7 3 5 9 4 8

Sample Output

4

题意：

给定长度为 $N$ 的一串整数序列 $a[1 sim N]$，求其最长上升子序列的长度。

注意：子序列可以不连续，要求严格单增。

题解：

$O(n log n)$ 解法——贪心+二分。

构建一个栈 $S$ 和一个变量 $top$ 代表栈顶位置，该栈的代表：栈中的第 $i$ 个数 $S[i]$，是序列 $a$ 中，长度为 $i$ 的递增子序列的末尾元素。

初始化 S[top=1]=a[1] ，即将第一个数字入栈；这很好理解，到目前为止 $a[1]$ 自己是一个长度为 $1$ 的递增子序列。

遍历 $a[ i = 2 sim N ]$：每次对于 $a[i]$，找出栈 $S[1 sim top]$ 中第一个大于等于 $a[i]$ 的数的位置 $pos$，若不存在则返回 $pos=top+1$。

这是由于，若存在第一个大于等于 $a[i]$ 的数 $S[pos]$ ，说明对于长度为 $pos$ 的递增子序列，可以用 $a[i]$ 代替掉其原来的末尾元素 $S[pos]$，这样一来，依然是一个长度为 $pos$ 的递增子序列，而且该递增子序列被进一步“加长”的潜力增加。而如果栈中不存在大于等于 $a[i]$ 的数，这说明我可以在目前长度为 $top$ 的递增子序列后面加上一个 $a[i]$，那么我们就得到了一个以 $a[i]$ 为结尾的，长度为 $top+1$ 的递增子序列。

因此，我们把 $S[pos]$ 更新为 $a[i]$，并且尝试更新栈的大小 if(pos>top) top=pos;  。

由于栈 $S$ 中元素始终保持单调递增（而且栈内元素互不相等），所以找 $S$ 中第一个大于等于 $a[i]$ 的数可以使用二分查找。

AC代码（在OpenJudge百练提交）：

PS.我们可以看到，求第一个大于等于 $a[i]$ 的数使用了lower_bound，相应的如果我们使用upper_bound会怎么样呢？不难证明，我们将会得到最长不下降子序列的长度。