Maximum path sum for each position with jumps under divisibility condition | PHP 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. ; Driven Program ; Function calling
< ? php function printMaxSum ( $ arr , $ n ) { $ dp = array ( ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { $ dp [ $ i ] = $ arr [ $ i ] ; $ maxi = 0 ; for ( $ 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 ( $ i = 0 ; $ i < $ n ; $ i ++ ) echo $ dp [ $ i ] , " ▁ " ; } $ arr = array ( 2 , 3 , 1 , 4 , 6 , 5 ) ; $ n = sizeof ( $ arr ) ; printMaxSum ( $ arr , $ n ) ; ? >