最长递增子序列解题思路

问题：

有序列[6, 2, 8, 7, 4, 3, 9, 10, 5]， 找到最长的递增子序列（非字串，可以不连续）

刚敲了一个硬币组合问题的代码，想着趁着手热，再刷个简单的动态规划问题，就看到了这个最长递增子序列的问题。拿到问题，第一眼，一脸懵逼中。这…状态方程怎么写？

用笔画了一下，如果只有一个数字（6），那结果肯定就是1了；那再加一个2呢？答案还是1（6 或者 2）；但是如果加的是8呢？答案就变成2了（6， 8）。

哦，那就是6可以跟后面任何一个连接，但是要满足递增的原则。这好像有点广搜的概念了。就是每个数都可以和后面的任何一个数连接。突然脑壳一亮，是不是所有的动态规划都可以先从广搜入手？这个有点意思，有待验证。

其实想到类似广搜的概念之后，这个状态转移的方程就好写多了。

F(N) = max{F(K) or F(k) + 1 if a[k] < a[N], k < N}

差不多就是这个意思了，代码不敲了。

期待更多的动态规划问题有类似广搜的解体思路。（事实证明广搜时间复杂度比较高，不推荐！）

备注：另外看到有个解法是用二分法解决的，很有意思，时间复杂度可以趋近于N，有兴趣的可以了解一下。