最长上升子序列空优异解分别是什么?

一、最长上升子序列空优异解

最长上升子序列（Longest Increasing Subsequence，LIS）问题是在给定序列中找到一个最长的子序列，使得子序列中的元素是严格递增的。在求解LIS问题时，我们可以使用不同的算法，这些算法在时间复杂度和空间复杂度方面具有不同的性能。

1、动态规划解法

动态规划（Dynamic Programming，DP）是解决LIS问题的常用方法之一。我们可以定义一个一维数组dp，其中dp[i]表示以第i个元素结尾的最长上升子序列的长度。通过遍历序列中的每个元素，我们可以找到以当前元素结尾的最长上升子序列。最后，整个序列的LIS长度等于dp数组中的最大值。

时间复杂度：动态规划解法的时间复杂度为O(n^2)，其中n为序列的长度。这是因为我们需要遍历序列中的每个元素，同时对于每个元素，我们还需要遍历其之前的所有元素以更新dp数组。

空间复杂度：动态规划解法的空间复杂度为O(n)，因为我们需要一个长度为n的dp数组来存储以每个元素结尾的最长上升子序列的长度。

2、基于二分查找的优化解法

在求解LIS问题时，我们还可以利用二分查找来优化时间复杂度。我们可以定义一个数组tails，其中tails[i]表示长度为i+1的上升子序列的最小末尾元素。通过遍历序列中的每个元素，并更新tails数组，我们可以找到最长的上升子序列。

时间复杂度：基于二分查找的优化解法的时间复杂度为O(nlogn)，其中n为序列的长度。这是因为我们需要遍历序列中的每个元素，同时对于每个元素，我们还需要进行O(logn)的二分查找操作以更新tails数组。

空间复杂度：基于二分查找的优化解法的空间复杂度为O(n)，因为我们需要一个长度为n的tails数组来存储长度为i+1的上升子序列的最小末尾元素。