Python中计算最长递增子序列的数量

在这个数组中，我们给出了一个大小为 N 的数组，我们的任务是给出给定数组的最长递增子序列的数量。

让我们看一些例子来理解这个问题。

输入： arr[] = [1, 1, 1, 1, 1, 1, 1]

输出 5

解释：最长的增长子序列，或 [1]，长度为 1。因此，有七个长度为一的最长增长子序列。

输入： arr[] = [1, 3, 5, 4, 7]

输出 2

解释：长度为 4 的最大上升子序列有两个，即 [1, 3, 4, 7] 和 [1, 3, 5, 7]，最长的增长子序列的长度为 4。

方法 - 1

这是解决这个问题的最基本方法。在此方法中，我们将生成给定数组中所有可能的子序列。在获得所有子序列后，我们将计算递增子序列的数量。我们将返回最大长度的递增子序列的数量。

这种方法的时间复杂度会非常高。程序需要指数时间来生成所有子序列。时间复杂度将为 2^N，其中 N 是数组的大小。在获得子序列后，我们必须运行另一个循环来计算递增子序列的数量。因此，总时间复杂度将为 O(N * 2^N)。

此方法的空间复杂度将用于存储子序列的数组的长度。

方法 - 2

我们将看到另一种方法，它比之前朴素的方法更优化，并且花费的时间更少。在这种方法中，我们将使用动态规划来解决上述问题。我们可以看到有大量的重叠情况，当消除这些情况时，可以大大降低时间复杂度。首先，我们将使用动态规划的制表或记忆化方法。

让我们看看这个问题的方法。

我们将通过初始化两个数组来开始解决方案。这两个数组将用作动态规划表。令这些数组为 dp_1 和 dp_2。我们将使用这些数组来存储最长递增子序列的长度以及到数组当前索引为止的此类序列的计数。

代码

输出

2

时间复杂度：此程序使用嵌套循环来获取递增子序列的最大长度。因此，时间复杂度将是二次方，即 O(N * 2)。

辅助空间：程序使用空间来存储递归堆栈和 dp 数组。因此，空间复杂度将是上述项目所需空间的平均值，即 O(N)。

方法 - 3

我们可以使用线段树来解决这个问题。我们将首先构建一个线段树，然后我们将在范围 [0, arr[i] - 1] 中查询，这是思路。解释是小于它的每个整数都可以附加 arr[i] 来创建一个递增子序列。

例如，如果 arr[i] = 5，则 arr[i] 可以添加到 0、1、2、3、4 之后，以创建递增子序列。我们将尝试通过线段树应用此逻辑。我们将有一个节点包含一对的线段树。该对包括以节点结尾的方式以及 LIS 的长度。树的基准将是我们的结果。

我们使用数组的最大值来创建线段树。如果它太大，我们必须使用 RANKING 技术来减小它。例如，[9, 1, 4, 2] 和 [3, 0, 2, 1] 的 LIS 计数是相同的。这是因为序列保持不变，正如您所见。利用这个概念，我们可以将线段树所需的空间减小到 O(4 * N)，其中 N 是数组的大小。

以上方法的实现如下：

代码

输出

2

时间复杂度：此方法的时间复杂度是对数级的。该程序将花费的总时间为 O(NlogN)，对于 N 个元素进行 logN 次查询。

辅助空间：此方法的空间复杂度为 O(N)。