数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序中递增子序列大小为3的最大乘积
在这个问题中，我们给定一个包含n个正整数的数组arr[]。我们的任务是创建一个程序来找到大小为3的递增子序列的最大乘积。
问题描述 − 在这里，我们需要找到数组中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.
使用自平衡二叉搜索树找到最小元素，对于最大元素，我们将从右到左遍历并找到右侧的最大元素。
找到这两个值后，我们将找到元素子数组的乘积，然后通过比较所有乘积来找到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
更新于: 2020年12月9日
117 次查看
广告