Maximize sum possible from an array by jumps of length i + K * arr [ i ] from any ith index | C ++ program for the above approach ; Function to find the maximum sum possible by jumps of length i + K * arr [ i ] from any i - th index ; Initialize an array dp [ ] ; Stores the maximum sum ; Iterate over the range [ N - 1 , 0 ] ; If length of the jump exceeds N ; Set dp [ i ] as arr [ i ] ; Otherwise , update dp [ i ] as sum of dp [ i + K * arr [ i ] ] and arr [ i ] ; Update the overall maximum sum ; Print the answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void maxSum ( int arr [ ] , int N , int K ) { int dp [ N + 2 ] = { 0 } ; int maxval = 0 ; for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( ( i + K * arr [ i ] ) >= N ) { dp [ i ] = arr [ i ] ; } else { dp [ i ] = dp [ i + K * arr [ i ] ] + arr [ i ] ; } maxval = max ( maxval , dp [ i ] ) ; } cout << maxval ; } int main ( ) { int arr [ ] = { 2 , 1 , 3 , 1 , 2 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int K = 3 ; maxSum ( arr , N , K ) ; return 0 ; }