昨天晚上看蓝书，看到了LIS问题的优化解法。

是比O(n方)更快的解法，实际上是一个常数优化。

先讲一下朴素的解法：

一个集合a，a[i]是第i个元素。设dp[i]为以编号为i的元素结尾的最长不上升子序列。

找到状态转移：

dp[i] = max{dp[j]}+1  (j < i && a[j] >= a[i])

这样的解法是O(n)的。

 

如何让它更快，我们可以先推出一个结论：

长度相同的序列，最后元素或者最前元素后于另一个序列的最后元素或者最前元素的序列更优。

证明：

dp[i]是编号i元素结尾的最长不上升子序列，所以这个子序列的结尾是编号i。

前一个导弹越高，更可能拦截下一个导弹，所以a[i]越大越好。

在当前最长不上升子序列中，只有最后一个元素决定了下一个导弹是否被拦截，由上上一行得到子序列中（不上升）最后一个元素越大越好。

所以，我们的命题就变成了：长度相同的子序列（不上升），越往后，子序列的最后一个元素越大。

因为如果较往后的序列一定选中了较往前的序列中没有的数字，而且它的最后一个元素显然不可能被前序列选取，由于他们长度相同，所以它也一定舍弃了前序列的某些数字。

因为它们都是不上升子序列，由此可推出舍弃的元素一定小于后序列的最后一个元素（和某些元素），而最后一个元素（不管哪个序列）都一定是这个序列中最小的。

又因为前序列最后元素大于后序列某些元素，且后序列最后元素是其序列中最小的。

所以后序列最后元素大于前序列最后元素，证毕。

 

既然我们知道每一个长度的子序列在每个状态中都有最优解，我们就设g[i]是长度为i的最优子序列结尾的编号。

通过上述的证明，我们知道g[i]是长度为i的最优子序列（的结尾）。

然后使用一个变量t来记录当前求出的最长不上升子序列。

所以，从g[t],g[t-1],g[t-2] ... g[1] 遍历，一旦找到其中一个结尾高于当前元素（i），我们就可以得到dp[i]。这时候，因为我们的i一定比g[dp[i]]大，所以我们更新g[dp[i]]。

然后通过dp[i]来更新t，t = max(t,dp[i])。

这样，优化就完成了。