Given an array of n positive integers. Initially we are at first position. We can jump to position y (1 <= y <= n) from position x (1 <= x <= n) if x divides y and x < y. The task is to print maximum sum path ending at every position x.
Note : Since first element is at position 1, we can jump to any position from here as 1 divides all other position numbers.
Examples :
Input : arr[] = {2, 3, 1, 4, 6, 5}
Output : 2 5 3 9 8 10
Explanation:
Maximum sum path ending with position 1 is 2.
For position 1, last position to visit is 1 only.
So maximum sum for position 1 = 2.
Maximum sum path ending with position 2 is 5.
For position 2, path can be jump from position 1
to 2 as 1 divides 2.
So maximum sum for position 2 = 2 + 3 = 5.
For position 3, path can be jump from position 1
to 3 as 1 divides 3.
So maximum sum for position 3 = 2 + 1 = 3.
For position 4, path can be jump from position 1
to 2 and 2 to 4.
So maximum sum for position 4 = 2 + 3 + 4 = 9.
For position 5, path can be jump from position 1
to 5.
So maximum sum for position 5 = 2 + 6 = 8.
For position 6, path can be jump from position
1 to 2 and 2 to 6 or 1 to 3 and 3 to 6.
But path 1 -> 2 -> 6 gives maximum sum for
position 6 = 2 + 3 + 5 = 10.
Approach:
The idea is to use Dynamic Programming to solve this problem.
Create an 1-D array dp[] where each element dp[i] stores maximum sum path ending at index i (or position x where x = i+1) with divisible jumps. The recurrence relation for dp[i] can be defined as: dp[i] = max(dp[i], dp[divisor of i+1] + arr[i]) To find all the divisor of i+1, move from 1 divisor to sqrt(i+1).
Below is the implementation of this approach:
C++
// C++ program to print maximum // path sum ending with // each position x such that all // path step positions // divide x. #include <bits/stdc++.h> using namespace std; void printMaxSum(int arr[], int n) { // Create an array such that dp[i] // stores maximum // path sum ending with i. int dp[n]; memset(dp, 0, sizeof dp); // Calculating maximum sum path // for each element. for (int i = 0; i < n; i++) { dp[i] = arr[i]; // Finding previous step for arr[i] // Moving from 1 to sqrt(i+1) since all the // divisors are present from sqrt(i+1). int maxi = 0; for (int j = 1; j <= sqrt(i + 1); j++) { // Checking if j is divisor of i+1. if (((i + 1) % j == 0) && (i + 1) != j) { // Checking which divisor will provide // greater value. 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; } // Printing the answer (Maximum path sum ending // with every position i+1. for (int i = 0; i < n; i++) cout << dp[i] << " "; } // Driven Program int main() { int arr[] = { 2, 3, 1, 4, 6, 5 }; int n = sizeof(arr) / sizeof(arr[0]); printMaxSum(arr, n); return 0; } |
Java
// Java program to print maximum path // sum ending with each position x such // that all path step positions divide x. import java.util.*; class GFG { static void printMaxSum(int arr[], int n) { // Create an array such that dp[i] // stores maximum path sum ending with i. int dp[] = new int[n]; Arrays.fill(dp, 0); // Calculating maximum sum // path for each element. for (int i = 0; i < n; i++) { dp[i] = arr[i]; // Finding previous step for arr[i] // Moving from 1 to sqrt(i+1) since all the // divisors are present from sqrt(i+1). int maxi = 0; for (int j = 1; j <= Math.sqrt(i + 1); j++) { // Checking if j is divisor of i+1. if (((i + 1) % j == 0) && (i + 1) != j) { // Checking which divisor will // provide greater value. 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; } // Printing the answer (Maximum path sum // ending with every position i+1.) for (int i = 0; i < n; i++) System.out.print(dp[i] + " "); } // Driver code public static void main(String[] args) { int arr[] = { 2, 3, 1, 4, 6, 5 }; int n = arr.length; // Function calling printMaxSum(arr, n); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to print maximum # path sum ending with each position # x such that all path step positions # divide x. def printMaxSum(arr, n): # Create an array such that dp[i] # stores maximum path sum ending with i. dp = [0 for i in range(n)] # Calculating maximum sum path # for each element. for i in range(n): dp[i] = arr[i] # Finding previous step for arr[i] # Moving from 1 to sqrt(i + 1) since all the # divisors are present from sqrt(i + 1). maxi = 0 for j in range(1, int((i + 1) ** 0.5) + 1): # Checking if j is divisor of i + 1. if ((i + 1) % j == 0 and (i + 1) != j): # Checking which divisor will provide # greater value. if (dp[j - 1] > maxi): maxi = dp[j - 1] if (dp[(i + 1) // j - 1] > maxi and j != 1): maxi = dp[(i + 1) // j - 1] dp[i] += maxi # Printing the answer # (Maximum path sum ending # with every position i + 1). for i in range(n): print(dp[i], end = ' ') # Driver Program arr = [2, 3, 1, 4, 6, 5] n = len(arr) printMaxSum(arr, n) # This code is contributed by Soumen Ghosh. |
C#
// C# program to print maximum path // sum ending with each position x such // that all path step positions divide x. using System; class GFG { static void printMaxSum(int[] arr, int n) { // Create an array such that dp[i] // stores maximum path sum ending with i. int[] dp = new int[n]; // Calculating maximum sum // path for each element. for (int i = 0; i < n; i++) { dp[i] = arr[i]; // Finding previous step for arr[i] // Moving from 1 to sqrt(i+1) since all the // divisors are present from sqrt(i+1). int maxi = 0; for (int j = 1; j <= Math.Sqrt(i + 1); j++) { // Checking if j is divisor of i+1. if (((i + 1) % j == 0) && (i + 1) != j) { // Checking which divisor will // provide greater value. 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; } // Printing the answer (Maximum path sum ending // with every position i+1.) for (int i = 0; i < n; i++) Console.Write(dp[i] + " "); } // Driver code public static void Main() { int[] arr = { 2, 3, 1, 4, 6, 5 }; int n = arr.Length; // Function calling printMaxSum(arr, n); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to print maximum path sum ending with // each position x such that all path step positions // divide x. function printMaxSum($arr, $n) { // Create an array such that dp[i] stores maximum // path sum ending with i. $dp = array() ; // Calculating maximum sum path for each element. for ($i = 0; $i < $n; $i++) { $dp[$i] = $arr[$i]; // Finding previous step for arr[i] // Moving from 1 to sqrt(i+1) since all the // divisors are present from sqrt(i+1). $maxi = 0; for ($j = 1; $j <= sqrt($i + 1); $j++) { // Checking if j is divisor of i+1. if ((($i + 1) % $j == 0) && ($i + 1) != $j) { // Checking which divisor will provide // greater value. 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; } // Printing the answer (Maximum path sum ending // with every position i+1. for ($i = 0; $i < $n; $i++) echo $dp[$i] , " " ; } // Driven Program $arr = array(2, 3, 1, 4, 6, 5 ); $n = sizeof($arr); printMaxSum($arr, $n); // This code is contributed by Ryuga ?> |
Javascript
<script> // Javascript program to print maximum path // sum ending with each position x such // that all path step positions divide x. function printMaxSum(arr, n) { // Create an array such that dp[i] // stores maximum path sum ending with i. let dp = new Array(n); dp.fill(0); // Calculating maximum sum // path for each element. for (let i = 0; i < n; i++) { dp[i] = arr[i]; // Finding previous step for arr[i] // Moving from 1 to sqrt(i+1) since all the // divisors are present from sqrt(i+1). let maxi = 0; for (let j = 1; j <= Math.sqrt(i + 1); j++) { // Checking if j is divisor of i+1. if (((i + 1) % j == 0) && (i + 1) != j) { // Checking which divisor will // provide greater value. if (dp[j - 1] > maxi) maxi = dp[j - 1]; if (dp[parseInt((i + 1) / j, 10) - 1] > maxi && j != 1) maxi = dp[parseInt((i + 1) / j, 10) - 1]; } } dp[i] += maxi; } // Printing the answer (Maximum path sum ending // with every position i+1.) for (let i = 0; i < n; i++) document.write(dp[i] + " "); } let arr = [ 2, 3, 1, 4, 6, 5 ]; let n = arr.length; // Function calling printMaxSum(arr, n); </script> |
Output
2 5 3 9 8 10
Time Complexity: O(n*sqrt(n)).
Auxiliary Space: O(n)
This article is contributed by Anuj Chauhan. If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!