C++-এ Number of Longest Increasing Subsequence

এই সমস্যায় একটি আনসর্টেড পূর্ণসংখ্যার অ্যারে দেওয়া থাকলে, লংগেস্ট ইনক্রিজিং সাবসিকোয়েন্স (LIS) কতটি আছে তা বের করতে হবে।

উদাহরণ: [1,3,5,4,7] -> আউটপুট 2। LIS গুলো: [1,3,5,7] এবং [1,3,4,7]।

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

len[i] = ইন্ডেক্স i-এ শেষ হওয়া LIS-এর দৈর্ঘ্য।
cnt[i] = ঐ দৈর্ঘ্যের LIS-এর সংখ্যা।
প্রতিটি i এর জন্য সব j < i চেক করুন:
- যদি nums[i] > nums[j]:
  - যদি len[j] + 1 > len[i]: len[i] = len[j] + 1, cnt[i] = cnt[j]।
  - যদি len[j] + 1 == len[i]: cnt[i] += cnt[j]।
গ্লোবাল maxLen ট্র্যাক করুন।
শেষে len[i] == maxLen হলে ans += cnt[i]।

উদাহরণ (C++)

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

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> len(n, 1), cnt(n, 1);
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1;
                        cnt[i] = cnt[j];
                    } else if (len[j] + 1 == len[i]) {
                        cnt[i] += cnt[j];
                    }
                }
            }
            maxLen = max(maxLen, len[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++)
            if (len[i] == maxLen) ans += cnt[i];
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 3, 5, 4, 7};
    cout << ob.findNumberOfLIS(v);
    return 0;
}

ইনপুট

[1,3,5,4,7]