Chúng tôi được cung cấp với một mảng các số nguyên có kích thước N. Mục tiêu ở đây là tìm Tập hợp con sản phẩm tối đa và tối thiểu. Chúng tôi sẽ thực hiện việc này bằng cách lấy hai biến sản phẩm, một cho sản phẩm tối thiểu được tìm thấy cho đến nay minProd và một cho sản phẩm tối đa được tìm thấy cho đến nay, maxProd.
Trong khi duyệt qua mảng, chúng ta sẽ nhân từng phần tử với cả minProd và maxProd. Đồng thời kiểm tra sản phẩm tối đa trước đó, sản phẩm tối thiểu trước đó, sản phẩm tối đa hiện tại, sản phẩm tối thiểu hiện tại và chính yếu tố hiện tại.
Đầu vào
Arr[]= { 1,2,5,0,2 } Đầu ra
Maximum Product: 20 Minimum Product: 0
Giải thích - Bắt đầu từ phần tử thứ hai trong mảng với các giá trị maxProd và minProd được khởi tạo bằng 1 (phần tử đầu tiên).
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
Đầu vào
Arr[]= { -1,2,-5,0,2 } Đầu ra
Maximum Product: 20 Minimum Product: -20
Giải thích - Đối với sản phẩm tối đa, tập hợp con có các phần tử- {-1,2, -5,2}
Đối với sản phẩm tối thiểu, tập hợp con có các phần tử- {2, -5,2}
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Mảng số nguyên Arr [] chứa các số nguyên dương và âm.
-
Kích thước biến chứa độ dài của mảng.
-
Hàm getProductSubset (int arr [], int n) nhận mảng làm đầu vào và trả về tích tối đa và tối thiểu của các phần tử thu được.
-
Các biến curMin, curMax được sử dụng để lưu trữ sản phẩm tối đa và tối thiểu hiện tại được tìm thấy. Ban đầu là arr [0].
-
Các biến trướcMin, trướcMax được sử dụng để lưu trữ sản phẩm tối đa và tối thiểu được tìm thấy trước đó. Ban đầu là arr [0].
-
Các biến maxProd và minProd được sử dụng để lưu trữ các sản phẩm tối đa và tối thiểu cuối cùng thu được.
-
Bắt đầu duyệt qua mảng từ phần tử thứ 2, arr [1] cho đến chỉ mục cuối cùng.
-
Để có sản phẩm tối đa, nhân arr [i] hiện tại với trướcMax và trướcMin. Lưu trữ tối đa sản phẩm trong curMax. Nếu curMax này> presMax, hãy cập nhật curMax bằng trước.
-
Cập nhật maxProd với curMax nếu curMax> maxProd.
-
Ở lần cập nhật cuối cùng, ưu tiên sử dụng curMax cho lần lặp lại tiếp theo.
-
Thực hiện các bước tương tự như trên đối với presMin, curMin và minProd bằng cách thay đổi các so sánh.
-
In kết quả thu được trong maxProd và minProd sau khi vòng lặp kết thúc.
Ví dụ
#include <iostream>
using namespace std;
void getProductSubset(int arr[], int n){
// Initialize all products with 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;
// Process all elements after arr[0]
for (int i = 1; i < n; ++i){
/* Current maximum product is maximum of following
1) prevMax * current arr[i] (when arr[i] is +ve)
2) prevMin * current arr[i] (when arr[i] is -ve)
3) current arr[i]
4) Previous max product */
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;
/* Current minimum product is minimum of following
1) prevMin * current arr[i] (when arr[i] is +ve)
2) prevMax * current arr[i] (when arr[i] is -ve)
3) current arr[i]
4) Previous min product */
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;
// copy current values to previous values
prevMax = curMax;
prevMin = curMin;
}
std::cout<<"Maximum Subset Product: "<<maxProd;
std::cout<<"\nMinimum Subset Product: "<<minProd;
}
int main(){
int Arr[] = {-4, -3, 1, 2, 0, 8, 1};
// int arr[] = {-4, 1,1, 3, 5,7};
int size = 7;
getProductSubset(Arr,size ) ;
return 0;
} Đầu ra
Maximum Subset Product: 192 Minimum Subset Product: -64