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ụ là tìm tích lớn nhất của một bộ ba (tập con kích thước 3) trong mảng. Ta sẽ tìm bộ ba cho giá trị tích lớn nhất và trả về tích đó.
Ví dụ minh họa
Đầu vào
arr[] = {9, 5, 2, 11, 7, 4}
Đầu ra
693
Giải thích
Tìm bộ ba cho tích lớn nhất:
maxProd = 9 * 11 * 7 = 693
Phương pháp giải
Có nhiều cách giải. Chúng ta thảo luận 3 phương pháp:
Phương pháp 1: Trực tiếp (O(n³))
Lặp qua mảng tìm tất cả bộ ba có thể. Tính tích và trả về lớn nhất.
Thuật toán
Khởi tạo
maxProd = -1000
Bước 1: Tạo 3 vòng lặp lồng nhau
Vòng 1: i -> 0 đến n-3
Vòng 2: j -> i đến n-2
Vòng 3: k -> j đến n-1
Bước 1.1
Tìm tích, prod = arr[i]*arr[j]*arr[k]
Bước 1.2
if prod > maxProd -> maxProd = prod
Bước 3
Trả về maxProd
Chương trình minh họa
#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 << "Tích lớn nhất bộ ba trong mảng là " << calcMaxProd(arr, n);
return 0;
}
Đầu ra
Tích lớn nhất bộ ba trong mảng là 693
Phương pháp 2: Sắp xếp (O(n log n))
Sắp xếp mảng giảm dần. Trong mảng đã sắp xếp, bộ ba tích lớn nhất sẽ ở:
(arr[0], arr[1], arr[2]) - ba số lớn nhất
(arr[0], arr[n-1], arr[n-2]) - số lớn nhất và hai số nhỏ nhất (có thể âm)
Trả về lớn nhất của hai tích này.
Thuật toán
Bước 1: Sắp xếp mảng giảm dần.
Bước 2:
maxTriplet1 = arr[0]*arr[1]*arr[2]
maxTriplet2 = arr[0]*arr[n-1]*arr[n-2]
Bước 3: if(maxTriplet1 > maxTriplet2) -> trả về maxTriplet1
Bước 4: else -> trả về maxTriplet2.
Chương trình minh họa
#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 << "Tích lớn nhất bộ ba trong mảng là " << calcMaxProd(arr, n);
return 0;
}
Đầu ra
Tích lớn nhất bộ ba trong mảng là 693
Phương pháp 3: Tìm trực tiếp 5 giá trị quan trọng (O(n))
Bộ ba tích lớn nhất chỉ có thể từ 2 trường hợp:
(max, second_max, third_max)
(max, min, second_min)
Ta có thể tìm trực tiếp 5 giá trị này bằng một lần duyệt mảng.
Thuật toán
Khởi tạo
max = -1000, secMax = -1000, thirdMax = -1000
min = 1000, secMin = 1000
Bước 1: Duyệt mảng i = 0 đến n-1
Bước 1.1: if(arr[i] > max) -> thirdMax = secMax, secMax = max, max = arr[i]
Bước 1.2: else if(arr[i] > secMax) -> thirdMax = secMax, secMax = arr[i]
Bước 1.3: else if(arr[i] > thirdMax) -> thirdMax = arr[i]
Bước 1.4: if(arr[i] < min) -> secMin = min, min = arr[i]
Bước 1.5: else if(arr[i] < secMin) -> secMin = arr[i]
Bước 2: triplet1 = max * secMax * thirdMax; triplet2 = max * min * secMin
Bước 3: if(triplet1 > triplet2) -> trả về triplet1
Bước 4: else -> trả về triplet2
Chương trình minh họa
#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 << "Tích lớn nhất bộ ba trong mảng là " << calcMaxProd(arr, n);
return 0;
}
Đầu ra
Tích lớn nhất bộ ba trong mảng là 693