找出长度为 3 且具有最大乘积的递增子序列
原文： https://www.geeksforgeeks.org/increasing-subsequence-of-length-three-with-maximum-product/
给定一个非负整数序列，找到长度为 3 的子序列，该子序列具有最大乘积，且该子序列的数量按升序排列。
例子：
Input:
arr[] = {6, 7, 8, 1, 2, 3, 9, 10}
Output:
8 9 10
Input:
arr[] = {1, 5, 10, 8, 9}
Output: 5 8 9
由于我们要找到最大乘积，因此需要为给定序列中的每个元素找到以下两件事：
LSL：给定元素。
左侧最大的较小元素 LGR：在给定元素右边的最大最大元素。
找到元素的 LSL 和 LGR 之后，就可以找到元素与其 LSL 和 LGR 的乘积（如果它们都存在）。 我们为每个元素计算该乘积，并返回所有乘积的最大值。
简单方法是使用嵌套循环。 外循环按顺序遍历每个元素。 在外部循环内，运行两个内部循环（一个接一个）以查找当前元素的 LSL 和 LGR。 该方法的时间复杂度为 O(n^2)。
我们可以在O(nLogn)时间中执行。 为简单起见，让我们首先创建两个大小为n的数组LSL[]和LGR[]，其中n是输入数组arr[]中的元素数。 主要任务是填充两个数组LSL[]和LGR[]。 一旦我们填充了这两个数组，我们就需要找到最大乘积LSL[i] * arr[i] * LGR[i]，其中0 < i < n-1（请注意LSL[i]在i = 0时不存在，而i = n-1时LGR[i]不存在。 我们可以在O(nLogn)时间中填写LSL[]。 这个想法是使用像 AVL 这样的平衡二分搜索树。 我们从空的 AVL 树开始，在其中插入最左边的元素。 然后，我们从第二个元素开始到倒数第二个元素遍历输入数组。 对于当前正在遍历的每个元素，我们在 AVL 树中找到它的底面。 如果存在楼层，则将楼层存储在LSL[]中，否则将存储 NIL。 存储地板后，我们将当前元素插入 AVL 树中。
我们可以在O(n)时间中将填充LGR []。 这个想法类似于这个帖子。 我们从右侧遍历并跟踪最大元素。 如果最大元素大于当前元素，则将其存储在LGR[]中，否则将存储 NIL。
最后，我们运行O(n)循环，返回LSL[i] * arr[i] * LGR[i]的最大值。
此方法的总体复杂度为O(nLogn) + O(n) + O(n)，即O(nLogn)。 所需的辅助空间为O(n)。 请注意，我们可以避免 LSL 所需的空间，我们可以在最终循环中找到并使用 LSL 值。
版权属于：月萌API www.moonapi.com，转载请注明出处
