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