Tổng đường dẫn tối đa cho mỗi vị trí có các bước nhảy theo điều kiện chia hết trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm tổng đường dẫn tối đa cho mỗi vị trí với các bước nhảy theo điều kiện chia hết

Đối với điều này, chúng tôi sẽ được cung cấp một mảng n số nguyên ngẫu nhiên. Nhiệm vụ của chúng ta là nhảy từ vị trí này sang vị trí khác nếu nó chia nó và cuối cùng cung cấp đường dẫn tổng tối đa cho mọi vị trí nhất định.

Ví dụ

#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;
}

Đầu ra

2 5 3 9 8 10