Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm n số nguyên. Nhiệm vụ của chúng ta là tìm tích tối đa của một bộ ba (dãy con có kích thước 3) trong mảng. Ở đây, chúng tôi sẽ tìm bộ ba với giá trị sản phẩm tối đa và sau đó trả lại sản phẩm.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {9, 5, 2, 11, 7, 4} Đầu ra
693
Giải thích
Ở đây, chúng ta sẽ tìm bộ ba cho tích tối đa của tất cả các phần tử của mảng. maxProd =9 * 11 * 7 =693
Phương pháp tiếp cận giải pháp
Có thể có nhiều giải pháp cho vấn đề. Chúng ta sẽ thảo luận về chúng ở đây,
Phương pháp 1
Phương pháp trực tiếp Trong phương pháp này, chúng ta sẽ lặp trực tiếp qua mảng và sau đó tìm tất cả các bộ ba có thể có. Tìm tích các phần tử của mỗi bộ ba và trả về giá trị tối đa của tất cả chúng.
Thuật toán
Khởi tạo
maxProd = −1000
Bước 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
Bước 1.1 -
Find the product, prod = arr[i]*arr[j]*arr[k].
Bước 1.2 -
if prod > maxProd −> maxProd = prod.
Bước 3 -
return maxProd.
Ví dụ
Chương trình hiển thị việc triển khai giải pháp của chúng tôi,
#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;
} Đầu ra
Maximum product of a triplet in array is 693
Phương pháp 2
Sử dụng sắp xếp
Trong phương pháp này, chúng ta sẽ sắp xếp mảng theo thứ tự giảm dần. Trong mảng đã sắp xếp, bộ ba sản phẩm tối đa sẽ là,
(arr[0], arr[1], arr[2]) (arr[0], arr[1], arr[2])
Chúng tôi sẽ trả lại tối đa sản phẩm của những bộ ba này.
Thuật toán
Bước 1 -
Sort the given array in descending order.
Bước 2 -
Find product of triples, maxTriplet1 = arr[0]*arr[1]*arr[2] maxTriplet2 = arr[0]*arr[n−1]*arr[n−2]
Bước 3 -
if( maxTriplet1 > maxTriplet2 ) −> return maxTriplet1
Bước 4 -
else −> return maxTriplet2.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
Tích tối đa của một bộ ba trong mảng là 693
Phương pháp 3
Tìm giá trị bộ ba.
Như bây giờ chúng ta biết rằng bộ ba sản phẩm tối đa có thể là từ một trong hai bộ ba,
(maximum, second_max, third_max) (maximum, minimum, second_min)
Vì vậy, chúng ta có thể tìm trực tiếp các giá trị này bằng cách duyệt qua mảng và sau đó sử dụng các giá trị, chúng ta sẽ tìm thấy bộ ba tích số tối đa.
Thuật toán
Khởi tạo
max =-1000, secMax =-1000, thirdMax =-1000, min =10000, secMin =10000
Bước 1 -
loop the array i −> 0 to n−1.
Bước 1.1
if(arr[i] > max) −> thirdMax = secMax, secMax = max, max = arr[i]
Bước 1.2 -
elseif(arr[i] > secMax) −> thirdMax = secMax, secMax = arr[i]
Bước 1.3 -
elseif(arr[i] > thirdMax) −> thirdMax = arr[i]
Bước 1.4 -
if(arr[i] < min) −> secMin = min, min = arr[i]
Bước 1.4 -
elseif(arr[i] < secMin) −> secMin = arr[i]
Bước 2 -
triplet1 = max * secMax * thridMax triplet2 = max * min * secMin
Bước 3 -
if(triplet1 > triplet2) −> return triplet1
Bước 4 -
else −> return triplet2
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
Maximum product of a triplet in array is 693