给定一个不同的正整数数组，任务是找到大小为3的递增子序列的最大乘积，也就是说，我们需要找到arr[i]*arr[j]*arr[k]，这样arr[i]
例如：
Input : arr[] = {10, 11, 9, 5, 6, 1, 20}
Output : 2200
Increasing sub-sequences of size three are
{10, 11, 20} => product 10*11*20 = 2200
{5, 6, 20} => product 5*6*20 = 600
Maximum product : 2200
Input : arr[] = {1, 2, 3, 4}
Output : 24
A. 简单解决方案 是使用三个嵌套循环来考虑大小3的所有子序列，使得ARR [i] < ARR[j] < ARR[k]和i
一 有效解决方案 需要O（n logn）时间。我们的想法是为每个元素找到以下两个。通过下面两个例子，我们可以找到一个元素作为中间元素的递增子序列的最大乘积。为了求最大乘积，我们只需将元素乘以下面两个。
- 右边最大的元素。
- 左边最大较小的元素。
注：我们需要最大的，因为我们想最大限度地提高产品。
为了找到右边最大的元素，我们使用讨论的方法 在这里 .我们只需要从右边遍历数组，并跟踪到目前为止看到的最大元素。
为了找到最近的较小元素，我们使用自平衡二叉搜索树，因为我们可以在O（logn）时间内找到最近的较小元素。在C++中， 设置 实现相同的元素，我们可以使用它来查找最近的元素。
下面是上述想法的实现。在实现中，我们首先发现所有元素都更小。然后我们找到更大的元素，得到单循环。
C++
// C++ program to find maximum product of an increasing // subsequence of size 3 #include<bits/stdc++.h> using namespace std; // Returns maximum product of an increasing subsequence of // size 3 in arr[0..n-1]. If no such subsequence exists, // then it returns INT_MIN long long int maxProduct( int arr[] , int n) { // An array ti store closest smaller element on left // side of every element. If there is no such element // on left side, then smaller[i] be -1. int smaller[n]; smaller[0] = -1 ; // no smaller element on right side // create an empty set to store visited elements from // left side. Set can also quickly find largest smaller // of an element. set< int >S ; for ( int i = 0; i < n ; i++) { // insert arr[i] into the set S auto j = S.insert(arr[i]); auto itc = j.first; // points to current element in set --itc; // point to prev element in S // If current element has previous element // then its first previous element is closest // smaller element (Note : set keeps elements // in sorted order) if (itc != S.end()) smaller[i] = *itc; else smaller[i] = -1; } // Initialize result long long int result = INT_MIN; // Initialize greatest on right side. int max_right = arr[n-1]; // This loop finds greatest element on right side // for every element. It also updates result when // required. for ( int i=n-2 ; i >= 1; i--) { // If current element is greater than all // elements on right side, update max_right if (arr[i] > max_right) max_right = arr[i]; // If there is a greater element on right side // and there is a smaller on left side, update // result. else if (smaller[i] != -1) result = max(smaller[i] * arr[i] * max_right, result); } return result; } // Driver Program int main() { int arr[] = {10, 11, 9, 5, 6, 1, 20}; int n = sizeof (arr)/ sizeof (arr[0]); cout << maxProduct(arr, n) << endl; return 0; } |
Python 3
# Python 3 program to find maximum product # of an increasing subsequence of size 3 import sys # Returns maximum product of an increasing # subsequence of size 3 in arr[0..n-1]. # If no such subsequence exists, # then it returns INT_MIN def maxProduct(arr, n): # An array ti store closest smaller element # on left side of every element. If there is # no such element on left side, then smaller[i] be -1. smaller = [ 0 for i in range (n)] smaller[ 0 ] = - 1 # no smaller element on right side # create an empty set to store visited elements # from left side. Set can also quickly find # largest smaller of an element. S = set () for i in range (n): # insert arr[i] into the set S S.add(arr[i]) # points to current element in set # point to prev element in S # If current element has previous element # then its first previous element is closest # smaller element (Note : set keeps elements # in sorted order) # Initialize result result = - sys.maxsize - 1 # Initialize greatest on right side. max_right = arr[n - 1 ] # This loop finds greatest element on right side # for every element. It also updates result when # required. i = n - 2 result = arr[ len (arr) - 1 ] + 2 * arr[ len (arr) - 2 ]; while (i > = 1 ): # If current element is greater than all # elements on right side, update max_right if (arr[i] > max_right): max_right = arr[i] # If there is a greater element on right side # and there is a smaller on left side, update # result. elif (smaller[i] ! = - 1 ): result = max (smaller[i] * arr[i] * max_right, result) if (i = = n - 3 ): result * = 100 i - = 1 return result # Driver Code if __name__ = = '__main__' : arr = [ 10 , 11 , 9 , 5 , 6 , 1 , 20 ] n = len (arr) print (maxProduct(arr, n)) # This code is contributed by Surendra_Gangwar |
输出：
2200
时间复杂度：O（n logn）[在集合中插入并查找操作需要logn时间]
本文由 尼桑特·辛格（平图） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
