C++-এ অ্যারে থেকে সর্বোচ্চ ও সর্বনিম্ন গুণফল সাবসেট বের করা

একটি পূর্ণসংখ্যার অ্যারে দেওয়া আছে। এর সাবসেটগুলোর মধ্যে সর্বোচ্চ ও সর্বনিম্ন গুণফল খুঁজে বের করতে হবে। এটি ডাইনামিক প্রোগ্রামিং বা ট্র্যাকিং পদ্ধতিতে সমাধান করা যায়।

উদাহরণ ১

Arr[] = { 1, 2, 5, 0, 2 }

আউটপুট: Maximum Product: 20 Minimum Product: 0

উদাহরণ ২

Arr[] = { -1, 2, -5, 0, 2 }

আউটপুট: Maximum Product: 20 Minimum Product: -20

ব্যাখ্যা: সর্বোচ্চ গুণফলের সাবসেট: {-1, 2, -5, 2}। সর্বনিম্ন গুণফলের সাবসেট: {2, -5, 2}।

অ্যালগরিদম

• প্রথম উপাদান দিয়ে curMax, curMin, prevMax, prevMin, maxProd, minProd ইনিশিয়ালাইজ করুন।
• দ্বিতীয় উপাদান থেকে ট্রাভার্স করুন। প্রতিটি উপাদানের জন্য বর্তমান সর্বোচ্চ ও সর্বনিম্ন গুণফল আপডেট করুন: prevMax * arr[i], prevMin * arr[i], arr[i], prevMax (সর্বোচ্চের জন্য) এবং prevMin (সর্বনিম্নের জন্য)।
• শেষে maxProd ও minProd আপডেট করুন।

C++ প্রোগ্রাম

#include <iostream>
using namespace std;

void getProductSubset(int arr[], int n) {
    int curMax = arr[0], curMin = arr[0];
    int prevMax = arr[0], prevMin = arr[0];
    int maxProd = arr[0], minProd = arr[0];

    for (int i = 1; i < n; ++i) {
        int temp1 = prevMax * arr[i];
        int temp2 = prevMin * arr[i];
        int temp3 = max(temp1, temp2);
        curMax = max(temp3, arr[i]);
        curMax = max(curMax, prevMax);

        temp1 = prevMax * arr[i];
        temp2 = prevMin * arr[i];
        temp3 = min(temp1, temp2);
        curMin = min(temp3, arr[i]);
        curMin = min(curMin, prevMin);

        maxProd = max(maxProd, curMax);
        minProd = min(minProd, curMin);

        prevMax = curMax;
        prevMin = curMin;
    }
    cout << "Maximum Subset Product: " << maxProd;
    cout << "\nMinimum Subset Product: " << minProd;
}

int main() {
    int Arr[] = {-4, -3, 1, 2, 0, 8, 1};
    int size = 7;
    getProductSubset(Arr, size);
    return 0;
}

আউটপুট: Maximum Subset Product: 192 Minimum Subset Product: -64