C++ में विभाज्यता शर्त के साथ जंप द्वारा प्रत्येक स्थिति के लिए अधिकतम योग पथ

सरणी दी गई है। स्थिति i से j पर जंप कर सकते हैं यदि j, i+1 को विभाजित करता है (1-आधारित इंडेक्सिंग)। प्रत्येक स्थिति के लिए अधिकतम योग पथ खोजें।

DP: dp[i] = इंडेक्स i तक अधिकतम योग। प्रत्येक i के लिए, i+1 के भाजक j खोजें और dp[j-1] से अधिकतम लें।

उदाहरण: {2, 3, 1, 4, 6, 5} → आउटपुट: 2 5 3 9 8 10।

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