C++-এ অপারেশন পেরফর্ম করে অ্যারেতে সর্বোচ্চ প্রোডাক্ট বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি অ্যারে দেওয়া থাকলে, N-1 অপারেশন করুন: 1. a[j] → a[i]×a[j] এবং a[i] মুছে দিন। 2. শুধু a[i] মুছে দিন (এটি শুধু একবার করা যাবে)। শেষে বাকি মানগুলোর গুণফল সর্বোচ্চ করুন।

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

1. নেগেটিভ সংখ্যা কাউন্ট করুন (cntneg) এবং শূন্য কাউন্ট করুন (cntzero)।
2. সবচেয়ে ছোট আבסলিউট ভ্যালুয় वाले নেগেটিভ নোড চিহ্নিত করুন (pos)।
3. নেগেটিভ সংখ্যা বিজোড় হলে, সেটি মুছে দিন (used[pos]=1)।
4. সব শূন্য এবং চিহ্নিত নেগেটিভ মুছে দিন (অপারেশন টাইপ ১)।
5. বাকি পজেটিভ সংখ্যাগুলো গুণ করুন (অপারেশন টাইপ ১)।
6. শেষে অপারেশন টাইপ ২ (সadece মুছে দেওয়া) একবার করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

void MaximumProduct(int a[], int n) {
    int cntneg = 0, cntzero = 0;
    int used[n] = {0};
    int pos = -1;
    
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) {
            used[i] = 1;
            cntzero++;
        }
        if (a[i] < 0) {
            cntneg++;
            if (pos == -1 || abs(a[pos]) > abs(a[i]))
                pos = i;
        }
    }
    if (cntneg % 2 == 1) used[pos] = 1;
    
    if (cntzero == n || (cntzero == n - 1 && cntneg == 1)) {
        for (int i = 0; i < n - 1; ++i)
            cout << 1 << " " << i + 1 << " " << i + 2 << endl;
        return;
    }
    
    int lst = -1;
    for (int i = 0; i < n; ++i) {
        if (used[i]) {
            if (lst != -1) cout << 1 << " " << lst + 1 << " " << i + 1 << endl;
            lst = i;
        }
    }
    if (lst != -1) cout << 2 << " " << lst + 1 << endl;
    
    lst = -1;
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            if (lst != -1) cout << 1 << " " << lst + 1 << " " << i + 1 << endl;
            lst = i;
        }
    }
}

int main() {
    int a[] = {5, -2, 0, 1, -3};
    int n = sizeof(a) / sizeof(a[0]);
    MaximumProduct(a, n);
    return 0;
}

আউটপুট

2 3
1 1 2
1 2 4
1 4 5

ব্যাখ্যা

অ্যারে: [5, -2, 0, 1, -3]

নেগেটিভ: -2, -3 (বিজোড়) → সবচেয়ে ছোট abs: -2 (ইন্ডেক্স ১) → মুছে দিন

শূন্য: ইন্ডেক্স ২ → মুছে দিন

বাকি: 5, 1, -3 → গুণফল = -15 (সর্বোচ্চ সম্ভব)

জটিলতা

• সময়: O(n)
• স্থান: O(n)