C++-এ ক্রমবর্ধমান সাবসিকোয়েন্স-এর সর্বোচ্চ গুণফল বের করার প্রোগ্রাম

সমস্যা বিবরণ

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

সমাধানের পদ্ধতি (DP - LIS variant)

1. mpis[i] = ইন্ডেক্স i-এ শেষ হওয়া ক্রমবর্ধমান সাবসিকোয়েন্স-এর সর্বোচ্চ গুণফল।
2. ইনিশিয়াল: mpis[i] = arr[i]।
3. i = 1 থেকে n-1, j = 0 থেকে i-1:
   • যদি arr[i] > arr[j] এবং mpis[i] < mpis[j] * arr[i], তবে mpis[i] = mpis[j] * arr[i]।
4. mpis অ্যারেতে সর্বোচ্চ মান রিটার্ন করুন।

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

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

ll lis(ll arr[], ll n) {
    ll mpis[n];
    for (int i = 0; i < n; i++)
        mpis[i] = arr[i];
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && mpis[i] < (mpis[j] * arr[i]))
                mpis[i] = mpis[j] * arr[i];
    return *max_element(mpis, mpis + n);
}

int main() {
    ll arr[] = {3, 100, 4, 5, 150, 6};
    ll n = sizeof(arr) / sizeof(arr[0]);
    printf("%lld", lis(arr, n));
    return 0;
}

আউটপুট

45000

ব্যাখ্যা

সাবসিকোয়েন্স: 3, 100, 150 → গুণফল = 3 × 100 × 150 = 45000

জটিলতা

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