Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm các số nguyên và một số k. Ourtask là tạo một chương trình để tìm Tích số tối đa của dãy con có kích thước k trong C ++.
Mô tả sự cố - Ở đây, chúng ta cần tìm dãy con có kích thước k, 1 <=k <=n có tích lớn nhất trong các phần tử của nó.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {1, 5, 6, -2, 0, 4} , k = 3 Đầu ra
120
Giải thích
Con của kích thước 3 có tích tối đa là (5, 6, 4). Sản phẩm là 120.
Cách tiếp cận giải pháp
Để giải quyết vấn đề này, trước tiên chúng ta sẽ sắp xếp mảng arr [] và sau đó dựa trên các thành phần của arr [] và giá trị của k. Phương thức thay đổi như trong các trường hợp sau -
Trường hợp 1 (nếu k chẵn) - Tích có thể có tất cả các giá trị k lớn nhất trừ 0. Ở đây, chúng ta cũng cần quan tâm đến các cặp giá trị âm. Vì độ lớn của chúng cũng có thể cho kết quả là cực đại.
Trường hợp 2 (nếu k là số lẻ) - Đây là một điều kiện hơi phức tạp và các giá trị xác định cách kết quả cần được tính toán. Trường hợp này cần được phân loại thêm dựa trên phần tử tối đa của mảng.
Trường hợp 2.1 (nếu số tối đa là số dương) - điều này có nghĩa là mảng là một hỗn hợp của số dương và số âm. Trong trường hợp này, chúng tôi sẽ tìm tối đa k phần tử và cũng tìm kiếm các cặp tối đa từ phía phủ định (nếu có thể có thể cho kết quả).
Trường hợp 2.2 (nếu số tối đa là 0) - Điều này có nghĩa là mảng chứa tất cả các phần tử âm và không. Trong trường hợp này, kết quả tối đa sẽ là 0, vì nhân một số lẻ các phần tử âm sẽ dẫn đến một số âm, có nghĩa là 0 là tích lớn nhất.
Trường hợp 2.3 (nếu số tối đa là âm) - Điều này có nghĩa là mảng chỉ chứa các số âm. Trong trường hợp này, kết quả tối đa sẽ được cung cấp bằng cách nhân các phần tử có độ lớn tối thiểu, tức là mảng tối đa sẽ hữu ích.
Theo cách này, chúng ta cần kiểm tra giá trị của các phần tử cũng như k để có kết quả tối ưu. Đối với điều này, chúng tôi sẽ giữ inarray cả hai bên max và min để kiểm tra xem kết quả có thể mang lại hay không bằng cách nhân các cặp âm với kết quả.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int findMaxSubArrayProduct(int arr[], int n, int k) {
sort(arr, arr + n);
int maxProd = 1;
int i = 0, j = 0;
int maxprod, minprod;
if (arr[n - 1] == 0 && (k % 2 == 1))
return 0;
if (arr[n - 1] <= 0 && (k % 2 == 1)) {
for (i = n - 1; i >= n - k; i--)
maxProd *= arr[i];
return maxProd;
}
i = 0;
j = n - 1;
if (k % 2 == 1) {
maxProd *= arr[j];
j--;
k--;
}
k = k/2;
int it = 0;
while(it < k){
int minprod = arr[i] * arr[i + 1];
int maxprod = arr[j] * arr[j - 1];
if (minprod > maxprod) {
maxProd *= minprod;
i += 2;
} else {
maxProd *= maxprod;
j -= 2;
}
it++;
}
return maxProd;
}
int main() {
int arr[] = { 1, 5, 6, -2, 0, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout<<"The maximum product of subsequence of size "<<k<<" is "<<findMaxSubArrayProduct(arr, n, k);
return 0;
} Đầu ra
The maximum product of subsequence of size 3 is 120