C++-এ অ্যারেতে সর্বোচ্চ গুণফল ক্যাড্রাপল (সাবসিকোয়েন্স আকার ৪) (Maximum product quadruple (sub-sequence of size 4) in array)

এই সমস্যায় একটি অ্যারে arr[] দেওয়া আছে। আমাদের C++-এ অ্যারেতে সর্বোচ্চ গুণফল ক্যাড্রাপল (৪ উপাদানের সাবসিকোয়েন্স) বের করার প্রোগ্রাম লিখতে হবে।

কোড বিবরণ - ৪ উপাদানের সাবসিকোয়েন্স খুঁজে বের করতে হবে যাতে তাদের গুণফল সর্বোচ্চ হয়।

উদাহরণ:

ইনপুট

arr[] = {4, -2, 5, -6, 8}

আউটপুট

840

ব্যাখ্যা

ক্যাড্রাপল (-3, 5, -7, 8) এর গুণফল ৮৪০।

সমাধানের পদ্ধতি

একাধিক পদ্ধতি আছে:

1. ব্রুট ফোর্স: সব ক্যাড্রাপল চেক করুন (O(n⁴))
2. ৪টি সর্বোচ্চ ও ৪টি ন্যূনতম উপাদান বের করে ৩টি কেস চেক করুন: mx1*mx2*mx3*mx4, mn1*mn2*mn3*mn4, mx1*mx2*mn1*mn2
3. সর্ট করে প্রথম ৪ ও শেষ ৪ উপাদান নিয়ে উপরের ৩ কেস চেক করুন

উদাহরণ (ব্রুট ফোর্স)

#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 "<
আউটপুট
Maximum product of quadruple is 480
উদাহরণ (অপ্টিমাইজড)
#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++) {
        // update minimums
        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]; }
        // update maximums
        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 "<
আউটপুট
Maximum product of quadruple is 480
উদাহরণ (সর্টিং)
#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 "<
আউটপুট
Maximum product of quadruple is 480