Cho một mảng số nguyên kích thước N. Mục tiêu là tìm Tích lớn nhất và Tích nhỏ nhất của các tập con. Chúng ta sẽ dùng hai biến tích: minProd cho tích nhỏ nhất tìm thấy và maxProd cho tích lớn nhất.
Khi duyệt mảng, nhân mỗi phần tử với cả minProd và maxProd. Cần kiểm tra tích lớn nhất trước, tích nhỏ nhất trước, tích lớn nhất hiện tại, tích nhỏ nhất hiện tại và chính phần tử hiện tại.
Ví dụ 1
Đầu vào: Arr[] = { 1, 2, 5, 0, 2 }
Đầu ra: Tích lớn nhất: 20, Tích nhỏ nhất: 0
Giải thích: Bắt đầu từ phần tử thứ 2 với maxProd và minProd khởi tạo bằng 1 (phần tử đầu).
Arr[1]: 1*2=2, 1*2=2, maxProd=2, minProd=1 Arr[2]: 2*5=10, 1*5=5, maxProd=10, minProd=1 Arr[3]: 10*0=0, 1*0=0, maxProd=10, minProd=0 Arr[4]: 10*2=20, 0*2=0, maxProd=20, minProd=0
Ví dụ 2
Đầu vào: Arr[] = { -1, 2, -5, 0, 2 }
Đầu ra: Tích lớn nhất: 20, Tích nhỏ nhất: -20
Giải thích: Cho tích lớn nhất, tập con gồm { -1, 2, -5, 2 }. Cho tích nhỏ nhất, tập con { 2, -5, 2 }.
Phương pháp trong chương trình
- Mảng nguyên Arr[] chứa số nguyên dương và âm.
- Biến size lưu độ dài mảng.
- Hàm getProductSubset(int arr[], int n) nhận mảng, trả về tích lớn nhất và nhỏ nhất.
- Biến curMin, curMax lưu tích lớn nhất/nhỏ nhất hiện tại, khởi tạo bằng arr[0].
- Biến prevMin, prevMax lưu tích lớn nhất/nhỏ nhất trước, khởi tạo bằng arr[0].
- Biến maxProd, minProd lưu kết quả cuối cùng.
- Duyệt từ phần tử thứ 2 (arr[1]) đến cuối.
- Với tích lớn nhất: nhân arr[i] với prevMax và prevMin, lấy max lưu vào curMax. Nếu curMax > prevMax thì cập nhật.
- Cập nhật maxProd với curMax nếu lớn hơn.
- Cập nhật prevMax = curMax cho vòng sau.
- Làm tương tự cho minProd với các phép so sánh ngược.
- In kết quả sau vòng lặp.
Mã ví dụ
#include <iostream>
using namespace std;
void getProductSubset(int arr[], int n) {
// Khởi tạo tất cả tích bằng arr[0]
int curMax = arr[0];
int curMin = arr[0];
int prevMax = arr[0];
int prevMin = arr[0];
int maxProd = arr[0];
int minProd = arr[0];
int temp1 = 0, temp2 = 0, temp3 = 0;
// Xử lý các phần tử sau arr[0]
for (int i = 1; i < n; ++i) {
/* Tích lớn nhất hiện tại là max của:
1) prevMax * arr[i] (khi arr[i] dương)
2) prevMin * arr[i] (khi arr[i] âm)
3) arr[i] hiện tại
4) Tích lớn nhất trước */
temp1 = prevMax * arr[i];
temp2 = prevMin * arr[i];
temp3 = temp1 > temp2 ? temp1 : temp2;
curMax = temp3 > arr[i] ? temp3 : arr[i];
curMax = curMax > prevMax ? curMax : prevMax;
/* Tích nhỏ nhất hiện tại là min của:
1) prevMin * arr[i] (khi arr[i] dương)
2) prevMax * arr[i] (khi arr[i] âm)
3) arr[i] hiện tại
4) Tích nhỏ nhất trước */
temp1 = prevMax * arr[i];
temp2 = prevMin * arr[i];
temp3 = temp1 < temp2 ? temp1 : temp2;
curMin = temp3 < arr[i] ? temp3 : arr[i];
curMin = curMin < prevMin ? curMin : prevMin;
maxProd = maxProd > curMax ? maxProd : curMax;
minProd = minProd < curMin ? minProd : curMin;
// Sao chép giá trị hiện tại sang trước cho vòng sau
prevMax = curMax;
prevMin = curMin;
}
std::cout << "Tích tập con lớn nhất: " << maxProd;
std::cout << "\nTích tập con nhỏ nhất: " << minProd;
}
int main() {
int Arr[] = {-4, -3, 1, 2, 0, 8, 1};
int size = 7;
getProductSubset(Arr, size);
return 0;
}
Đầu ra
Tích tập con lớn nhất: 192 Tích tập con nhỏ nhất: -64