C++-এ অ্যারেতে ট্রিপলেট (সাবসিকোয়েন্স আকার ৩) এর সর্বোচ্চ গুণফল বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি ইন্টিজার অ্যারে দেওয়া থাকলে, যেকোনো তিনটি এলিমেন্ট (ট্রিপলেট) বের করুন যাতে তাদের গুণফল সর্বোচ্চ হয়। ক্রম বজায় রাখতে হয় না।

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

সবচেয়ে সহজ: তিনটি নেস্টেড লুপ (O(n³))। কিন্তু অপ্টিমাইজড পদ্ধতি:

1. অ্যারে সর্ট করুন।
2. সর্বোচ্চ গুণফল হবে এক из:
   • সর্বোচ্চ তিনটি পজেটিভ সংখ্যার গুণফল।
   • সর্বনিম্ন দুটি নেগেটিভ সংখ্যা × সর্বোচ্চ পজেটিভ সংখ্যা।

দ্রষ্টব্য: প্রদত্ত কোড O(n³) ব্রুট-ফোর্স ব্যবহার করেছে।

C++ কোড উদাহরণ (ব্রুট-ফোর্স)

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

int maxProduct(int arr[], int n) {
    if (n < 3) return -1;
    int max_product = INT_MIN;
    for (int i = 0; i < n - 2; i++)
        for (int j = i + 1; j < n - 1; j++)
            for (int k = j + 1; k < n; k++)
                max_product = max(max_product, arr[i] * arr[j] * arr[k]);
    return max_product;
}

int main() {
    int arr[] = {10, 3, 5, 6, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max = maxProduct(arr, n);
    if (max == -1)
        cout << "No Triplet Exists";
    else
        cout << "Maximum product is " << max;
    return 0;
}

আউটপুট

Maximum product is 1200

অপ্টিমাইজড সমাধান (O(n log n))

sort(arr, arr+n);
return max(arr[n-1]*arr[n-2]*arr[n-3], arr[0]*arr[1]*arr[n-1]);

জটিলতা

• ব্রুট-ফোর্স: O(n³)
• অপ্টিমাইজড: O(n log n)