資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告