贪心算法如何解决最长递增子序列问题？
贪心算法可以解决最长递增子序列问题，具体步骤如下：
- 定义状态：用一个数组Dp来记录以每个元素结尾的最长递增子序列的长度，初始时全部置为1。
- 遍历数组：从第一个元素开始遍历到最后一个元素，对于每个元素i，再从第一个元素遍历到i-1，如果nums[i]大于nums[j]，则更新Dp[i] = max(Dp[i], Dp[j] + 1)。
- 返回结果：最长递增子序列的长度即为Dp数组中的最大值。
贪心算法的关键在于每一步都选择当前最优的解决方案，而不考虑整体的最优解。对于最长递增子序列问题，贪心算法每次选择能使得当前子序列增长最快的元素，从而得到最终的最长递增子序列。
举个例子来说明，假设有数组nums = [10, 9, 2, 5, 3, 7, 101, 18]，使用贪心算法来求解最长递增子序列的长度：
- 初始化Dp数组为[1, 1, 1, 1, 1, 1, 1, 1]。
- 从第一个元素开始遍历：
- 对于元素9，此时Dp数组为[1, 1, 1, 1, 1, 1, 1, 1]，9无法构成递增子序列，Dp[1]仍为1。
- 对于元素2，此时Dp数组为[1, 1, 1, 1, 1, 1, 1, 1]，2无法构成递增子序列，Dp[2]仍为1。
- 对于元素5，此时Dp数组为[1, 1, 1, 1, 1, 1, 1, 1]，5可以与2构成递增子序列，更新Dp[3] = Dp[2] + 1 = 2。
- 对于元素3，此时Dp数组为[1, 1, 1, 2, 1, 1, 1, 1]，3无法构成递增子序列，Dp[4]仍为1。
- 对于元素7，此时Dp数组为[1, 1, 1, 2, 1, 1, 1, 1]，7可以与2、5构成递增子序列，更新Dp[6] = Dp[2] + 1 = 2。
- 对于元素101，此时Dp数组为[1, 1, 1, 2, 1, 2, 1, 1]，101可以与2、5、7构成递增子序列，更新Dp[7] = Dp[6] + 1 = 3。
- 对于元素18，此时Dp数组为[1, 1, 1, 2, 1, 2, 1, 3]，18可以与2、5、7构成递增子序列，更新Dp[8] = Dp[6] + 1 = 3。
- 最终Dp数组为[1, 1, 1, 2, 1, 2, 1, 3]，最长递增子序列的长度为3，即为[2, 5, 7]或[2, 5, 18]。
