C++ 中长度为 3 的递增子序列的最大乘积
在本教程中,我们将讨论一个查找长度为 3 的递增子序列的最大乘积的程序。
为此,将向我们提供一个正整数数组。我们的任务是找到三个元素的子序列,其乘积最大。
示例
#include<bits/stdc++.h> using namespace std; //returning maximum product of subsequence long long int maxProduct(int arr[] , int n) { int smaller[n]; smaller[0] = -1 ; set<int>S ; for (int i = 0; i < n ; i++) { auto j = S.insert(arr[i]); auto itc = j.first; --itc; if (itc != S.end()) smaller[i] = *itc; else smaller[i] = -1; } long long int result = INT_MIN; int max_right = arr[n-1]; for (int i=n-2 ; i >= 1; i--) { if (arr[i] > max_right) max_right = arr[i]; else if (smaller[i] != -1) result = max(smaller[i] * arr[i] * max_right, result); } return result; } 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; }
输出
2200
广告