C ++程序中大小为3的递增子序列的最大乘积
在这个问题中，我们得到了n个正整数的数组arr[]。我们的任务是创建一个程序来查找大小为3的子序列增加的Maximum产品。
问题描述-在这里，我们需要找到数组的3个元素的最大乘积，以使它们形成递增的子序列，并且数组索引也在增加，即
arr[i]*arr[j]*arr[k] is maximum, arr[i]<arr[j]<arr[k] and i<j<k
让我们举个例子来了解这个问题，
输入项
arr = {5, 9, 2, 11, 4, 7}输出结果
495
说明
All subarrays of size 3 satisfying the condition are (5, 9, 11), prod = 5*9*11 = 495 (2, 4, 7), prod = 2*4*7 = 56 Maximum = 495
解决方法
解决问题的一种简单方法是循环数组并找到满足给定条件的3的所有子数组。
查找元素的乘积并返回所有乘积的最大值。
算法
初始化-
maxProd = −1000
第1步-
Loop i −> 0 to n−3
步骤1.1-
Loop j −> i to n−2
步骤1.1.1-
if(arr[i]< arr[j]) −> loop k −> j to n−1
步骤1.1.1.1-
if(arr[j] < arr[k]) −> find prod = arr[i]*arr[j]*arr[k].
步骤1.1.1.2-
if(maxProd > prod) −> maxProd = prod.
第2步-
Return maxProd.
示例
该程序说明了我们解决方案的工作原理，
#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
int maxProd = −1000;
int prod;
for (int i = 0; i < n − 2; i++)
for (int j = i + 1; j < n − 1; j++)
if(arr[i] < arr[j]){
for (int k = j + 1; k < n; k++){
if(arr[j] < arr[k]){
prod = arr[i] * arr[j] * arr[k];
if(maxProd < prod)
maxProd = prod;
}
}
}
return maxProd;
}
int main(){
int arr[] = { 5, 9, 2, 11, 4, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum product of an increasing subsequence of size 3
is "<<calcMaxProd(arr, n);
return 0;
}输出结果
The maximum product of an increasing subsequence of size 3 is 495
该解决方案很简单，但是使用了3个嵌套循环，使时间复杂度达到O(n3)。因此，让我们来看一个有效的解决方案，
在此解决方案中，我们将采用数组的元素从索引1到n-2。并将其作为我们3元素子数组的中间元素。然后从数组中找到其余两个元素。
Element smaller than arr[i] in array with index less than i. Element greater than aar[i] in array with index more than i.
使用自平衡二进制搜索树找到最小的元素，对于最大的元素，我们将从右向左遍历并在右边找到最大的元素。
找到两个值之后，我们将找到元素子数组的prod，然后通过比较所有值来找到maxProd。
示例
该程序说明了我们解决方案的工作原理，
#include<bits/stdc++.h>
using namespace std;
long calMaxSubSeqProd(int arr[] , int n) {
int smallerLeftEle[n];
smallerLeftEle[0] = −1 ;
set<int>small ;
for (int i = 0; i < n ; i++) {
auto it = small.insert(arr[i]);
auto val = it.first;
−−val;
if (val != small.end())
smallerLeftEle[i] = *val;
else
smallerLeftEle[i] = −1;
}
long maxProd = −10000;
long prod ;
int greaterRightEle = arr[n−1];
for (int i= n−2 ; i >= 1; i−−) {
if (arr[i] > greaterRightEle)
greaterRightEle = arr[i];
else if (smallerLeftEle[i] != −1){
prod = smallerLeftEle[i]*arr[i]*greaterRightEle;
if(prod > maxProd)
maxProd = prod;
}
}
return maxProd;
}
int main() {
int arr[] = {5, 9, 2, 11, 4, 7};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum product of an increasing subsequence of size 3
is "<<calMaxSubSeqProd(arr, n);
return 0;
}输出结果
The maximum product of an increasing subsequence of size 3 is 495