Maximum path sum for each position with jumps under divisibility condition | Python3 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 divisiors are present from sqrt ( i + 1 ) . ; Checking if j is divisior of i + 1. ; Checking which divisor will provide greater value . ; Printing the answer ( Maximum path sum ending with every position i + 1 ) . ; Driver Program ;
def printMaxSum ( arr , n ) : NEW_LINE INDENT dp = [ 0 for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT dp [ i ] = arr [ i ] NEW_LINE maxi = 0 NEW_LINE for j in range ( 1 , int ( ( i + 1 ) ** 0.5 ) + 1 ) : NEW_LINE INDENT if ( ( i + 1 ) % j == 0 and ( i + 1 ) != j ) : NEW_LINE INDENT if ( dp [ j - 1 ] > maxi ) : NEW_LINE INDENT maxi = dp [ j - 1 ] NEW_LINE DEDENT if ( dp [ ( i + 1 ) // j - 1 ] > maxi and j != 1 ) : NEW_LINE INDENT maxi = dp [ ( i + 1 ) // j - 1 ] NEW_LINE DEDENT DEDENT DEDENT dp [ i ] += maxi NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT print ( dp [ i ] , end = ' ▁ ' ) NEW_LINE DEDENT DEDENT arr = [ 2 , 3 , 1 , 4 , 6 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE / * Function calling * / NEW_LINE printMaxSum ( arr , n ) NEW_LINE