এই টিউটোরিয়ালে, আমরা বিভাজ্য অবস্থার অধীনে লাফ সহ প্রতিটি অবস্থানের জন্য সর্বাধিক পাথ যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব
এর জন্য আমাদের এন এলোমেলো পূর্ণসংখ্যার একটি অ্যারে দেওয়া হবে। আমাদের কাজ হল এক অবস্থান থেকে অন্য অবস্থানে লাফ দেওয়া যদি এটি ভাগ করে দেয় এবং অবশেষে প্রতিটি প্রদত্ত অবস্থানের জন্য সর্বাধিক যোগফলের পথ প্রদান করে৷
উদাহরণ
#include <bits/stdc++.h> using namespace std; //finding maximum sum path 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