C++-এ বিভাজ্যতা শর্তে জাম্প দিয়ে প্রতিটি পজিশনের জন্য সর্বোচ্চ পাথ সম বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি অ্যারে দেওয়া থাকলে, প্রতিটি পজিশন i (১-বেসড) থেকে যেসব পজিশন j (j < i) i-কে ভাগ করে (i % j == 0), সেখানে থেকে জাম্প করা যায়। প্রতিটি পজিশনের জন্য সর্বোচ্চ পাথ সম বের করুন।

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

1. dp[i] = ইন্ডেক্স i (০-বেসড) এ শেষ হওয়া সর্বোচ্চ পাথ সম।
2. dp[i] = arr[i] ইনিশিয়ালাইজ।
3. i = 0 থেকে n-1:
   • i+1-এর সব ডিভাইজার j খুঁজুন (j <= sqrt(i+1))।
   • যদি j ডিভাইজার হয়, তবে j-1 এবং (i+1)/j - 1 চেক করুন।
   • সর্বোচ্চ dp মান যোগ করুন।

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

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

void printMaxSum(int arr[], int n) {
    int dp[n];
    memset(dp, 0, sizeof dp);
    for (int i = 0; i < n; i++) {
        dp[i] = arr[i];
        int maxi = 0;
        for (int j = 1; j <= sqrt(i + 1); j++) {
            if (((i + 1) % j == 0) && (i + 1) != j) {
                if (dp[j - 1] > maxi) maxi = dp[j - 1];
                if (dp[(i + 1) / j - 1] > maxi && j != 1) maxi = dp[(i + 1) / j - 1];
            }
        }
        dp[i] += maxi;
    }
    for (int i = 0; i < n; i++)
        cout << dp[i] << " ";
}

int main() {
    int arr[] = {2, 3, 1, 4, 6, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printMaxSum(arr, n);
    return 0;
}

আউটপুট

2 5 3 9 8 10

ব্যাখ্যা

ইন্ডেক্স (১-বেসড): 1: 2 2: 3 + dp[1]=2 → 5 3: 1 + dp[1]=2 → 3 4: 4 + max(dp[1],dp[2]) = 4+5=9 5: 6 + dp[1]=2 → 8 6: 5 + max(dp[1],dp[2],dp[3]) = 5+5=10

জটিলতা

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