# 找出长度为 3 且具有最大乘积的递增子序列 > 原文： [https://www.geeksforgeeks.org/increasing-subsequence-of-length-three-with-maximum-product/](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 []`。 这个想法类似于[这个帖子](https://www.geeksforgeeks.org/replace-every-element-with-the-greatest-on-right-side/)。 我们从右侧遍历并跟踪最大元素。 如果最大元素大于当前元素，则将其存储在`LGR[]`中，否则将存储 NIL。 最后，我们运行`O(n)`循环，返回`LSL[i] * arr[i] * LGR[i]`的最大值 此方法的总体复杂度为`O(nLogn) + O(n) + O(n)`，即`O(nLogn)`。 所需的辅助空间为`O(n)`。 请注意，我们可以避免 LSL 所需的空间，我们可以在最终循环中找到并使用 LSL 值。