Maximize sum possible from an array by jumps of length i + K * arr [ i ] from any ith index | 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
def maxSum ( arr , N , K ) : NEW_LINE INDENT dp = [ 0 for i in range ( N + 2 ) ] NEW_LINE maxval = 0 NEW_LINE i = N - 1 NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT if ( ( i + K * arr [ i ] ) >= N ) : NEW_LINE INDENT dp [ i ] = arr [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] = dp [ i + K * arr [ i ] ] + arr [ i ] NEW_LINE DEDENT maxval = max ( maxval , dp [ i ] ) NEW_LINE i -= 1 NEW_LINE DEDENT print ( maxval ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 1 , 3 , 1 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE K = 3 NEW_LINE maxSum ( arr , N , K ) NEW_LINE DEDENT