C++-এ অ্যারেতে সব বর্ধমান সাবসিকোয়েন্স গণনা (Count All Increasing Subsequences)

এই টিউটোরিয়ালে, ০ থেকে ৯ পর্যন্ত ডিজিট ধারণকারী একটি অ্যারেতে কতগুলো বর্ধমান সাবসিকোয়েন্স (increasing subsequences) আছে তা গণনা করার প্রোগ্রাম আলোচনা করা হয়েছে।

পদ্ধতি

DP অ্যারে count[10] ব্যবহার করুন যেখানে count[d] = d ডিজিট দিয়ে শেষ হওয়া বর্ধমান সাবসিকোয়েন্সের সংখ্যা। প্রতিটি উপাদানের জন্য ছোট ডিজিটগুলোর কাউন্ট যোগ করুন।

C++ প্রোগ্রাম উদাহরণ

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

int count_sequence(int arr[], int n) {
    int count[10] = {0};
    for (int i = 0; i < n; i++) {
        for (int j = arr[i] - 1; j >= 0; j--)
            count[arr[i]] += count[j];
        count[arr[i]]++;
    }
    int result = 0;
    for (int i = 0; i < 10; i++)
        result += count[i];
    return result;
}

int main() {
    int arr[] = {3, 2, 4, 5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << count_sequence(arr, n);
    return 0;
}

আউটপুট

14