ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่ประกอบด้วยจำนวนเต็ม n ตัว งานของเราคือค้นหาผลิตภัณฑ์สูงสุดของแฝดสาม (ลำดับต่อมาของขนาด 3) ในอาร์เรย์ ในที่นี้เราจะหาค่าสามเท่าที่มีมูลค่าผลิตภัณฑ์สูงสุดแล้วส่งคืนผลิตภัณฑ์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {9, 5, 2, 11, 7, 4} ผลลัพธ์
693
คำอธิบาย
ที่นี่ เราจะพบแฝดสามที่ให้ผลคูณสูงสุดขององค์ประกอบทั้งหมดของอาร์เรย์ maxProd =9 * 11 * 7 =693
แนวทางการแก้ปัญหา
อาจมีวิธีแก้ไขปัญหาได้หลายทาง เราจะมาพูดคุยกันที่นี่
วิธีที่ 1
วิธีการโดยตรง ในวิธีนี้ เราจะวนรอบอาร์เรย์โดยตรงแล้วค้นหาแฝดสามที่เป็นไปได้ทั้งหมด ค้นหาผลคูณขององค์ประกอบของแฝดสามแต่ละตัวและคืนค่าสูงสุดของพวกมันทั้งหมด
อัลกอริทึม
เริ่มต้น
maxProd = −1000
ขั้นตอนที่ 1 :
Create three nested loops: Loop 1:i −> 0 to n−3 Loop 2: j −> i to n−2 Loop 3: k −> j to n−1
ขั้นตอนที่ 1.1 −
Find the product, prod = arr[i]*arr[j]*arr[k].
ขั้นตอนที่ 1.2 −
if prod > maxProd −> maxProd = prod.
ขั้นตอนที่ 3 −
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++)
for (int k = j + 1; k < n; k++){
prod = arr[i] * arr[j] * arr[k];
if(maxProd < prod)
maxProd = prod;
}
return maxProd;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of a triplet in array is "<<calcMaxProd(arr, n);
return 0;
} ผลลัพธ์
Maximum product of a triplet in array is 693
วิธีที่ 2
การใช้การเรียงลำดับ
ในวิธีนี้ เราจะเรียงลำดับอาร์เรย์จากมากไปหาน้อย ในอาร์เรย์ที่เรียงลำดับ ผลิตภัณฑ์ triplet สูงสุดจะอยู่ที่
(arr[0], arr[1], arr[2]) (arr[0], arr[1], arr[2])
เราจะคืนผลิตภัณฑ์สูงสุดสำหรับแฝดสามเหล่านี้
อัลกอริทึม
ขั้นตอนที่ 1 −
Sort the given array in descending order.
ขั้นตอนที่ 2 −
Find product of triples, maxTriplet1 = arr[0]*arr[1]*arr[2] maxTriplet2 = arr[0]*arr[n−1]*arr[n−2]
ขั้นตอนที่ 3 −
if( maxTriplet1 > maxTriplet2 ) −> return maxTriplet1
ขั้นตอนที่ 4 −
else −> return maxTriplet2.
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
int calcMaxProd(int arr[], int n){
sort(arr, arr + n, greater<>());
int maxTriplet1 = arr[0]*arr[1]*arr[2];
int maxTriplet2 = arr[0]*arr[n−1]*arr[n−2];
if(maxTriplet1 > maxTriplet2)
return maxTriplet1;
return maxTriplet2;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of a triplet in array is
"<<calcMaxProd(arr, n);
return 0;
} ผลลัพธ์
ผลคูณสูงสุดของแฝดสามในอาร์เรย์คือ 693
วิธีที่ 3
การหาค่าแฝดสาม
ตอนนี้เราทราบแล้วว่าผลิตภัณฑ์แฝดสามสูงสุดอาจมาจากแฝดสามตัวใดตัวหนึ่งจากสองตัวนี้
(maximum, second_max, third_max) (maximum, minimum, second_min)
ดังนั้น เราสามารถหาค่าเหล่านี้ได้โดยตรงโดยผ่านอาร์เรย์ จากนั้นใช้ค่า เราจะหา triplet ของผลิตภัณฑ์สูงสุด
อัลกอริทึม
เริ่มต้น
max =-1000, secMax =-1000, thirdMax =-1000 , min =10000, secMin =10000
ขั้นตอนที่ 1 −
loop the array i −> 0 to n−1.
ขั้นตอนที่ 1.1
if(arr[i] > max) −> thirdMax = secMax, secMax = max, max = arr[i]
ขั้นตอนที่ 1.2 −
elseif(arr[i] > secMax) −> thirdMax = secMax, secMax = arr[i]
ขั้นตอนที่ 1.3 −
elseif(arr[i] > thirdMax) −> thirdMax = arr[i]
ขั้นตอนที่ 1.4 −
if(arr[i] < min) −> secMin = min, min = arr[i]
ขั้นตอนที่ 1.4 −
elseif(arr[i] < secMin) −> secMin = arr[i]
ขั้นตอนที่ 2 −
triplet1 = max * secMax * thridMax triplet2 = max * min * secMin
ขั้นตอนที่ 3 −
if(triplet1 > triplet2) −> return triplet1
ขั้นตอนที่ 4 −
else −> return triplet2
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
int max = −1000, secMax = −1000, thirdMax = −1000;
int min = 1000, secMin = 1000;
for (int i = 0; i < n; i++){
if (arr[i] > max){
thirdMax = secMax;
secMax = max;
max = arr[i];
}
else if (arr[i] > secMax){
thirdMax = secMax;
secMax = arr[i];
}
else if (arr[i] > thirdMax)
thirdMax = arr[i];
if (arr[i] < min){
secMin = min;
min = arr[i];
}
else if(arr[i] < secMin)
secMin = arr[i];
}
int triplet1 = max * secMax * thirdMax;
int triplet2 = max * secMin * min;
if(triplet1 > triplet2)
return triplet1;
return triplet2;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of a triplet in array is
"<<calcMaxProd(arr, n);
return 0;
} ผลลัพธ์
Maximum product of a triplet in array is 693
