Maximum path sum for each position with jumps under divisibility condition | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printMaxSum ( int arr [ ] , int n ) { int dp [ n ] ; memset ( dp , 0 , sizeof dp ) ; for ( int i = 0 ; i < n ; i ++ ) { dp [ i ] = arr [ i ] ; int maxi = 0 ; for ( int 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 ( int i = 0 ; i < n ; i ++ ) cout << dp [ i ] << " ▁ " ; } int main ( ) { int arr [ ] = { 2 , 3 , 1 , 4 , 6 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printMaxSum ( arr , n ) ; return 0 ; }