请问动态规划里的最长递增子系列问题

Question

请问动态规划里的最长递增子系列问题
为什么时间复杂度是 nlog2 的呀

Answer 1

1、暴力解法

• 所谓暴力解法，就是穷举所有情况。因为对于长度为 $n$ 的原序列，它的子序列总共有 $2^n$ 种情况，所以利用深度优先搜索枚举所有情况，然后取 "满足相邻两元素递增并且长度最长" 的子序列就是答案，当然这种方法肯定是不可取的，因为随着 $n$ 的不断变大，整个求解时间复杂度呈指数级增长。

2、朴素解法

• 朴素解法采用的是动态规划的思想。首先当然是设计状态。

  1）设计状态

• 对于数组序列 $a_i(1 \le i \le n)$，令 $f[i]$ 表示以第 $i$ 个数 $a_i$ 结尾的最长递增子序列的长度。
• 那么，我们考虑以第 $i$ 个数 $a_i$ 结尾的最长递增子序列，它在这个序列中的前一个数一定是 $a_j(1 \le j < i)$ 中的一个，所以，如果我们已经知道了 $f[j]$，那么就有 $f[i] = f[j] + 1$。显然，我们还需要满足 $a_j < a_i$ 这个递增的限制条件。

  2）状态转移方程

• 那么就可以得出状态转移方程：$$f[i] = \max_{j=1}^{i-1} (f[j] \ | \ a_j < a_i) + 1$$
• 这里 $f[j]$ 是 $f[i]$ 的子结构，而 $max(f[j])$ 是 $f[i]$ 的最优子结构，当然我们需要考虑一种情况，就是没有找到最优子结构的时候，例如：$i=1$ 或者 不存在 $a_j < a_i$ 的 $j$，此时 $f[i] = 1$，表示 $a_i$ 本身是一个长度为 $1$ 的最长递增子序列。
• $f[i]$ 数组可以通过两层循环来求解，如下图表所示：

-|-|-|-|-|-|-|-
$a[i]$|1|2|4|6|3|5|9
$f[i]$|1|2|3|4|3|4|5

3）时间复杂度分析

• 状态数 $f[...]$ 总共 $O(n)$ 个，状态转移的消耗为 $O(n)$，所以总的时间复杂度为 $O(n^2)$，所以对于这类问题，一般能够接受的 $n$ 的范围在千级别，也就是 $1000, 2000, 3000 ...$。如果是 $n=10000, 100000$ 的情况，就需要考虑优化了。
• 那么，下文将介绍最长单调子序列的优化算法，基于的是 贪心 的思想，为了方便理解，将 "单调" 一词替换为 "递增"。均以 最长递增子序列 为例进行讲解。