Trong bài toán này, chúng ta được cung cấp một mảng arr []. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm sản phẩm tối đa bốn (dãy con có kích thước 4) trong mảng trong C ++.
Mô tả mã - Ở đây, chúng ta cần tìm một bộ bốn (dãy con có kích thước 4) sao cho tích của tất cả các phần tử là cực đại.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {4, -2, 5, -6, 8} Đầu ra
840
Giải thích
Bộ bốn, (-3, 5, -7, 8) với sản phẩm 840.
Phương pháp tiếp cận giải pháp
Có thể có nhiều giải pháp cho một vấn đề nhất định.
Một giải pháp đơn giản là sử dụng phương pháp trực tiếp bằng cách duyệt qua mảng. Sau đó, tìm tất cả các phần tư có thể có trong mảng. Tìm sản phẩm của họ rồi so sánh để tìm ra sản phẩm tối đa gấp bốn lần.
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 <iostream>
using namespace std;
int max(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxProdQuad(int arr[], int n){
int maxProd = 0;
int prod = 1;
for (int i = 0; i <= n - 4; i++)
for (int j = i + 1; j <= n - 3; j++)
for (int k = j + 1; k <= n - 2; k++)
for (int l = k + 1; l <= n - 1; l++) {
prod = arr[i] * arr[j] * arr[k] * arr[l];
maxProd = max(maxProd, prod);
prod = 1;
}
return maxProd;
}
int main(){
int arr[] = {4, -2, 5, -6, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
return 0;
} Đầu ra
Maximum product of quadruple is 480
Một cách khác để tìm bộ bốn với tích lớn nhất là tìm bốn phần tử lớn nhất của mảng và bốn phần tử nhỏ nhất của mảng.
Giả sử mx1, mx2, mx3, mx4 là bốn số lớn nhất đầu tiên. Và mn1, mn2, mn3, mn4 là bốn số nhỏ nhất đầu tiên của mảng. Sau đó, tìm các giá trị của
1. mx1 * mx2 * mx3 * mx4 2. mn1 * mn2 * mn3 * mn4 3. mx1 * mx2 * mn1 * mn2
Và trả về giá trị tối đa trong ba giá trị sản phẩm này, giá trị này sẽ cho tổng sản phẩm tối đa gấp bốn lần. Và tất cả các trường hợp đều được xem xét.
Chương trình hiển thị việc triển khai thuật toán của chúng tôi
Ví dụ
#include <iostream>
using namespace std;
int max(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxProdQuad(int arr[], int n) {
int mx1 = -1000, mx2 = -1000, mx3 = -10000, mx4 = -1000;
int mn1 = 1000, mn2 = 1000, mn3 = 1000, mn4 = 1000;
for (int i = 0; i < n; i++) {
if(arr[i] < mn1){
mn4 = mn3;
mn3 = mn2;
mn2 = mn1;
mn1 = arr[i];
}
else if(arr[i] < mn2){
mn4 = mn3;
mn3 = mn2;
mn2 = arr[i];
}
else if(arr[i] < mn3){
mn4 = mn3;
mn3 = arr[i];
}
else if(arr[i] < mn4){
mn4 = arr[i];
}
if(arr[i] > mx1){
mx4 = mx3;
mx3 = mx2;
mx2 = mx1;
mx1 = arr[i];
}
else if(arr[i] > mx2){
mx4 = mx3;
mx3 = mx2;
mx2 = arr[i];
}
else if(arr[i] > mx3){
mx4 = mx3;
mx3 = arr[i];
}
else if(arr[i] > mx4){
mx4 = arr[i];
}
}
int maxVal = max ((mx1 * mx2 * mx3 * mx4), (mn1 * mn2 * mn3 * mn4));
maxVal = max(maxVal, (mx1 * mx2 * mn1 * mn2));
return maxVal;
}
int main() {
int arr[] = {4, -2, 5, -6, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
return 0;
} Đầu ra
Maximum product of quadruple is 480
Một cách tiếp cận khác có thể là sắp xếp mảng. Sau đó, bốn giá trị tối đa và bốn giá trị nhỏ nhất sẽ lần lượt là phần cuối và phần đầu của mảng. Sau đó, giải như trong giải pháp trên bằng cách tìm giá trị tối đa của ba kết hợp giá trị cực đại và cực tiểu.
Chương trình thể hiện việc triển khai phương pháp tiếp cận của chúng tôi
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int findMaxProdQuad(int arr[], int n){
sort(arr, arr + n);
int maxVal = max((arr[n-1] * arr[n-2] * arr[n-3] * arr[n-4]), (arr[0] *
arr[1] * arr[2] * arr[3]));
maxVal = max(maxVal, (arr[n-1] * arr[n-2] * arr[0] * arr[1]));
return maxVal;
}
int main(){
int arr[] = {4, -2, 5, -6, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
return 0;
} Đầu ra
Maximum product of quadruple is 480