C++-এ সর্বোচ্চ গুণফল সাবঅ্যারে (নেগেটিভ গুণফল কেস সহ) (Maximum Product Subarray | Added negative product case)

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

সমস্যা সমাধান - অ্যারেতে ধনাত্মক, ঋণাত্মক ও শূন্য থাকে। সাবঅ্যারে তৈরি করে তাদের গুণফল বের করে সর্বোচ্চ গুণফল বের করতে হবে।

উদাহরণ:

ইনপুট

arr[] = {-1, 2, -7, -5, 12, 6}

আউটপুট

5040

ব্যাখ্যা

সর্বোচ্চ গুণফলযুক্ত সাবঅ্যারে: {2, -7, -5, 12, 6}। গুণফল = ৫০৪০।

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

maxVal (বর্তমান পর্যন্ত সর্বোচ্চ গুণফল) এবং minVal (নেগেটিভ সর্বোচ্চ গুণফল) ম্যানেইন করুন। বর্তমান উপাদানের চিহ্ন অনুযায়ী আপডেট করুন:

• ধনাত্মক: maxVal ও minVal গুণ করুন
• শূন্য: সাবঅ্যারে ভাঙুন
• ঋণাত্মক: maxVal ও minVal বিনিময় করে গুণ করুন

উদাহরণ

#include <iostream>
using namespace std;
int min(int a, int b){
    if(a < b) return a;
    return b;
}
int max(int a, int b){
    if(a > b) return a;
    return b;
}
int CalcMaxProductSubArray(int arr[], int n) {
    int i = 0;
    int maxVal = -1000;
    int localMax = 1;
    int localMin = 1;
    int lastMax;
    while(i < n) {
        int currentVal = arr[i];
        if (currentVal > 0) {
            localMax = (localMax * currentVal);
            localMin = min(1, localMin * currentVal);
        }
        else if (currentVal < 0) {
            lastMax = localMax;
            localMax = (localMin * currentVal);
            localMin = (lastMax * currentVal);
        } else {
            localMin = 1;
            localMax = 0;
        }
        maxVal = max(maxVal, localMax);
        if (localMax <= 0)
            localMax = 1;
        i++;
    }
    return maxVal;
}
int main(){
    int arr[] = { -1, 2, -7, -5, 12, 6 };
    int n = 6;
    cout<<"The maximum product Subarray is "<
আউটপুট
The maximum product Subarray is 5040