# 找出長度為 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 值。