Tutorialspoint.dev

Maximum path sum for each position with jumps under divisibility condition

Given an array of n positive integers. Initially we are at first position. We can jump to position y (1 <= x <= 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
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 + 3 = 5.

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.



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
        # divisiors are present from sqrt(i + 1).
        maxi = 0
        for j in range(1, int((i + 1) ** 0.5) + 1):
  
            # Checking if j is divisior 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
?>


Output:

2 5 3 9 8 10

Time Complexity: O(n*sqrt(n)).

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter