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