Maximum path sum for each position with jumps under divisibility condition | Javascript program to print maximum path sum ending with each position x such that all path step positions divide x . ; Create an array such that dp [ i ] stores maximum path sum ending with i . ; Calculating maximum sum path for each element . ; Finding previous step for arr [ i ] Moving from 1 to sqrt ( i + 1 ) since all the divisors are present from sqrt ( i + 1 ) . ; Checking if j is divisor of i + 1. ; Checking which divisor will provide greater value . ; Printing the answer ( Maximum path sum ending with every position i + 1. ) ; Driver code ; Function calling
function printMaxSum ( arr , n ) { let dp = new Array ( n ) ; dp . fill ( 0 ) ; for ( let i = 0 ; i < n ; i ++ ) { dp [ i ] = arr [ i ] ; let maxi = 0 ; for ( let j = 1 ; j <= Math . sqrt ( i + 1 ) ; j ++ ) { if ( ( ( i + 1 ) % j == 0 ) && ( i + 1 ) != j ) { 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 ; } for ( let i = 0 ; i < n ; i ++ ) document . write ( dp [ i ] + " " ) ; } let arr = [ 2 , 3 , 1 , 4 , 6 , 5 ] ; let n = arr . length ; printMaxSum ( arr , n ) ;