C++の除算条件でジャンプする各位置の最大パス合計

このチュートリアルでは、除算条件の下でジャンプを使用して各位置の最大パス合計を見つけるプログラムについて説明します

このために、n個のランダムな整数の配列が提供されます。私たちのタスクは、ある位置から別の位置にジャンプして分割し、最終的にすべての位置に最大の合計パスを提供することです。

例

#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